Submission #212946

#	Time	Username	Problem	Language	Result	Execution time	Memory
212946		popovicirobert	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5 ms	384 KiB

joitter2

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

struct DSU {
	vector<int> par, sz;
	int n;
	inline void init(int _n) {
		n = _n;
		par.resize(n + 1), sz.resize(n + 1, 1);
	}
	int root(int x) {
		return (par[x] == 0 ? x : par[x] = root(par[x]));
	}
	inline void join(int x, int y) {
		x = root(x), y = root(y);
		if(x != y) {
			sz[y] += sz[x];
			par[x] = y;
		}
	}
};



int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

   	cin >> n >> m;

   	vector<map<int, int>> mpc(n + 1);
   	map<pair<int, int>, vector<int>> ids;
   	vector<set<int>> in(n + 1);
   	// mpc[x][y] = comp. x are muchie la comp. y

   	DSU dsu; dsu.init(n);
   	ll ans = 0;
   	while(m--) {
   		int x, y; cin >> x >> y;
   		int xx = dsu.root(x), yy = dsu.root(y);
   		if(xx != yy) {
	   		if(mpc[yy][xx]) {
	   			ans -= 1LL * dsu.sz[xx] * (dsu.sz[xx] - 1) + 1LL * dsu.sz[yy] * (dsu.sz[yy] - 1);
	   			ans -= 1LL * (int)in[xx].size() * dsu.sz[xx];
	   			ans -= 1LL * (int)in[yy].size() * dsu.sz[yy];
	   			
	   			for(auto id : ids[{yy, xx}]) {
	   				in[xx].erase(id);
	   			}
	   			ids[{yy, xx}].clear();

	   			/*if((int)in[xx].size() + (int)mpc[xx].size() > (int)in[yy].size() + (int)mpc[yy].size()) {
	   				for(auto it : in[yy]) {
	   					if(in[xx].count(it) == 0) {
	   						mpc[dsu.root(it)][xx]++;
	   						in[xx].insert(it);
	   						ids[{dsu.root(it), xx}].push_back(it);
	   					}
	   				}
	   				for(auto it : mpc[yy]) {
	   					mpc[xx][it.first] += it.second;
	   				}
	   				swap(xx, yy);
	   			}
	   			else {*/
	   				for(auto it : in[xx]) {
	   					if(in[yy].count(it) == 0) {
	   						mpc[dsu.root(it)][yy]++;
	   						in[yy].insert(it);
	   						ids[{dsu.root(it), yy}].push_back(it);
	   					}
	   				}
	   				for(auto it : mpc[xx]) {
	   					mpc[yy][it.first] += it.second;
	   				}
	   			//}
	   			dsu.join(xx, yy);
	   			ans += 1LL * dsu.sz[yy] * (int)in[yy].size();
	   			ans += 1LL * dsu.sz[yy] * (dsu.sz[yy] - 1);
	   		}
	   		else {
		   		if(in[yy].count(x) == 0) {
					mpc[xx][yy]++;
					ans += dsu.sz[yy];
					in[yy].insert(x);
					ids[{xx, yy}].push_back(x);
				}
			}
   		}
   		cout << ans << "\n";
   	}

   	/*for(auto it : in[dsu.root(1)]) {
   		cerr << it << " " << mpc[dsu.root(it)][dsu.root(1)] << "\n";	
   	}*/

    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83