oj.uz

답안 #212919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212919 2020-03-24T14:19:07 Z popovicirobert 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 4 ms 384 KB 
#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>> mpe(n + 1), mpc(n + 1);
   	map<pair<int, int>, vector<int>> ids;
   	vector<set<int>> in(n + 1);
   	// mpe[x][y] = x are muchie la comp. y
   	// 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 * mpc[yy][xx] * dsu.sz[xx];
	   			
	   			ans += 1LL * (int)in[yy].size() * dsu.sz[xx];
	   			for(auto id : ids[{yy, xx}]) {
	   				in[xx].erase(id);
	   			}
	   			ids[{yy, xx}].clear();
	   			ans += 1LL * (int)in[xx].size() * dsu.sz[yy];

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

    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -