oj.uz

답안 #766730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766730 2023-06-26T05:39:38 Z qwerasdfzxcl 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 7 ms 14408 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

set<int> G[100100];
ll ans;

struct DSU{
	ll path[100100], sz[100100];
	set<int> st[100100], elem[100100];

	void init(int n){
		for (int i=1;i<=n;i++){
			path[i] = i;
			st[i].clear();
			elem[i].clear();
			elem[i].insert(i);
			sz[i] = 1;
		}
	}

	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}

	void merge(int x, int y){
		// printf(" merge %d %d\n", x, y);
		x = find(x), y = find(y);
		assert(x!=y);

		if (st[x].size() + elem[x].size() < st[y].size() + elem[y].size()) swap(x, y);

		ans -= (ll)st[x].size() * sz[x];
		ans -= (ll)st[y].size() * sz[y];
		ans -= sz[x] * (sz[x]-1);
		ans -= sz[y] * (sz[y]-1);
		// printf(" delete -> %lld\n", ans);

		for (auto p:st[y]) if (find(p)!=x){
			st[x].insert(p);
			G[find(p)].insert(x);
		} 

		for (auto p:elem[y]){
			auto iter = st[x].find(p);
			if (iter!=st[x].end()) st[x].erase(iter);
			elem[x].insert(p);
			G[x].insert(find(p));
		}

		sz[x] += sz[y];
		ans += st[x].size() * sz[x];
		ans += sz[x] * (sz[x]-1);
		// printf(" add -> %lld (%d %d)\n", ans, (int)st[x].size(), sz[x]);

		path[y] = x;
	}

	void insert(int x, int y){
		y = find(y);
		if (st[y].find(x)!=st[y].end()) return;

		ans += sz[y];
		st[y].insert(x);
		G[find(x)].insert(y);
	}
}dsu;

void update(int x, int y){
	int cx = dsu.find(x), cy = dsu.find(y);
	if (cx==cy) return;
	
	if (G[cy].find(cx)!=G[cy].end()) dsu.merge(cx, cy);
	
	else dsu.insert(x, cy);
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);

	dsu.init(n);

	for (int i=1;i<=m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		update(x, y);
		printf("%lld\n", ans);
	}
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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