Untitled
unknown
plain_text
a year ago
3.1 kB
9
Indexable
Never
#include <chrono> #include <iostream> using namespace std; using namespace std::chrono; #define opt __attribute((optimize("Ofast"))) #define MAX_STUDENT 100001 #define NO_COLOR 0 #define BLUE 1 #define PINK 2 int T, tc, n, m, f1, f2; char gender; bool isBoy[MAX_STUDENT]; int color[MAX_STUDENT]; int inversion; int wear; int line = 0; template <typename TYPE> class Vector { public: TYPE* data; int size; int capacity; Vector() { size = 0; capacity = 10; data = new TYPE[10]; } void reset() { size = 0; capacity = 10; delete[] data; data = new TYPE[10]; } void push(TYPE value) { if (size == capacity) { capacity *= 10; TYPE* temp = new TYPE[capacity]; for (int i = 0; i < size; i++) { temp[i] = data[i]; } delete[] data; data = temp; } data[size++] = value; } }; class Node { public: Vector <int> relation; int getRelation(int i) { return relation.data[i]; } } nodes[MAX_STUDENT]; void backtrack(int current, int previousColor) { if (wear >= n) return; if (color[current] == previousColor) { inversion = -1; wear = n + 1; return; } else if (color[current] != NO_COLOR) return; color[current] = (previousColor == PINK) ? BLUE : PINK; wear++; if ((isBoy[current] && color[current] == PINK) || (!isBoy[current] && color[current] == BLUE)) inversion++; for (int i = 0; i < nodes[current].relation.size; i++) { backtrack(nodes[current].getRelation(i), color[current]); } } opt int main(int argc, char** argv) { //84ms ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("input.txt", "r", stdin); auto st = high_resolution_clock::now(); cin >> T; line++; for (tc = 1; tc <= T; ++tc) { inversion = 0; wear = 0; cin >> n >> m; line++; //cout << "Size: " << line << " " << n << endl; line++; for (int i = 1; i <= n; i++) { cin >> gender; if (gender == 'B') isBoy[i] = true; else isBoy[i] = false; nodes[i].relation.reset(); color[i] = NO_COLOR; //cout << i << endl; } // Relationship for (int i = 0; i < m; i++) { cin >> f1 >> f2; line++; nodes[f1].relation.push(f2); nodes[f2].relation.push(f1); } backtrack(1, BLUE); if (inversion > (n / 2)) inversion = n - inversion; if (wear < n) { inversion = -1; } cout << "#" << tc << " " << inversion << endl; } auto en = high_resolution_clock::now(); double T = duration_cast<nanoseconds>(en - st).count(); cout << T / 1e9 << endl; return 0; }