Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### iceman91's blog

By iceman91, 12 years ago,

Here is the link to the problem and here is the link to my solution. I am using a disjoint set data structure to store 2 kinds of elements x and !x. If x and y are in the same set then they have the same type. If !x and y are in same set then x can eat y. I keep getting WA. Does anybody has any idea about this?

• 0

| Write comment?
 » 4 years ago, # |   0 My Solution#include using namespace std; using ll = long long; struct DSU { int n; std::vector root; std::vector d; explicit DSU(int _n) : n(_n) { root.resize(n); d.resize(n); for (int i = 0; i < n; ++i) { root[i] = i; d[i] = 0; } } int Find(int x) { if (x == root[x]) return x; int par = root[x]; root[x] = Find(root[x]); d[x] += d[par]; return root[par]; } bool Unite(int x, int y, int type) { if (x >= n || y >= n) return true; int px = Find(x); int py = Find(y); int val = ((d[x] - d[y] - type) % 3 + 3) % 3; if (px == py) { return val != 0; } else { root[px] = py; d[px] = 3 - val; return false; } } }; class StrangeFoodChain { public: void solve(std::istream& cin, std::ostream& cout) { int _t = 1; cin >> _t; for (int _tc = 1; _tc <= _t; ++_tc) { int n, k; cin >> n >> k; DSU dsu(n); int ans = 0; for (int i = 0; i < k; ++i) { int type, x, y; cin >> type >> x >> y; x--, y--, type--; ans += dsu.Unite(x, y, type); } cout << ans << '\n'; } } }; int32_t main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); StrangeFoodChain solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; } 
•  » » 4 weeks ago, # ^ |   0 can you describe the logic behind this solution....