Untitled
Pink and Blue Wrong Answerptrdung
c_cpp
a year ago
2.0 kB
8
Indexable
#include <iostream> using namespace std; int N; // number of Students int M; // number of friendships int friendship[200002][3], visited[200002]; int gender[100002]; // 1: Boy, 2: Girl int shirt[100002]; // 1: Blue, 2: Pink int hasfriend[100000]; char temp; int ans; int total; int temp1; void DFS(int a, int s) { if(ans == -1) return; total++; shirt[a] = s; if(shirt[a] != gender[a]) temp1++; for(int i = 1; i <= 2 * M; i++) { if(friendship[i][0] == a && visited[i] == 0) { if(shirt[friendship[i][1]] != 0) { //cout << friendship[i][0] << " " << friendship[i][1]; ans = -1; return; } else { visited[i] =1; if(friendship[i-1][0] == friendship[i][1] && friendship[i-1][1] == friendship[i][0]) visited[i-1] = 1; if(friendship[i+1][0] == friendship[i][1] && friendship[i+1][1] == friendship[i][0]) visited[i+1] = 1; DFS(friendship[i][1], 3-s); } } } } int main() { //freopen("input1.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++) { ans = 0; cin >> N >> M; for(int i = 1; i <= N; i++) { shirt[i] = 0; hasfriend[i] = 0; cin >> temp; if(temp == 'B') gender[i] = 1; else gender[i] = 2; } for(int i = 1; i <= M; i++) { cin >> friendship[2*i-1][0] >> friendship[2*i-1][1]; friendship[2*i][0] = friendship[2*i-1][1]; friendship[2*i][1] = friendship[2*i-1][0]; hasfriend[friendship[2*i-1][0]] = 1; hasfriend[friendship[2*i-1][1]] = 1; visited[2*i-1] =0; visited[2*i]= 0; } for(int i = 1; i <= N; i++) { if(hasfriend[i] == 0) shirt[i] = gender[i]; } for(int i = 1; i <= N; i++) { if(ans == -1) break; if(shirt[i] == 0) { temp1 = 0; total = 0; DFS(i, 1); if(ans == -1) break; if(temp1 > total /2) ans = ans + total - temp1; else ans = ans + temp1; } } cout << ans << endl; } return 0; }
Editor is loading...
Leave a Comment