oj.uz

답안 #766733

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

using namespace std;
typedef long long ll;

set<int> G[100100];
ll ans;
queue<pair<int, int>> mergeQ;

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);
		if (x==y) return;

		if (st[x].size() + elem[x].size() + G[x].size() < st[y].size() + elem[y].size() + G[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);

			if (G[x].find(find(p))!=G[x].end()) mergeQ.emplace(x, find(p));
		} 

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

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

		sz[x] += sz[y];
		ans += (ll)st[x].size() * sz[x];
		ans += sz[x] * (sz[x]-1);
		// printf(" add -> %lld (%d %lld)\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()){
		mergeQ.emplace(cx, cy);
		while(!mergeQ.empty()){
			auto [p, q] = mergeQ.front(); mergeQ.pop();
			dsu.merge(p, q);
		}
	} 
	
	else dsu.insert(x, cy);
}

int adj[55][55];
int naive(int n, int x, int y){
	adj[x][y] = 1;

	while(true){
		int flag = 0;
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				for (int k=1;k<=n;k++) if (i!=j && j!=k && i!=k){
					if (flag) break;
					if (adj[i][j] && adj[j][k] && adj[k][j] && !adj[i][k]){
						adj[i][k] = 1;
						flag = 1;
					}
				}
				if (flag) break;
			}
			if (flag) break;
		}

		if (!flag) break;
	}

	int ret = 0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) ret += adj[i][j];
	}

	return ret;
}

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);
		// int tmp = naive(n, x, y);
		// printf("%lld (%d)\n", ans, tmp);
		// assert(tmp==ans);
		
		printf("%lld\n", ans);
	}
}

Compilation message

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 7 ms 14344 KB Output is correct
4 Correct 7 ms 14372 KB Output is correct
5 Incorrect 8 ms 14420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 7 ms 14344 KB Output is correct
4 Correct 7 ms 14372 KB Output is correct
5 Incorrect 8 ms 14420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 7 ms 14344 KB Output is correct
4 Correct 7 ms 14372 KB Output is correct
5 Incorrect 8 ms 14420 KB Output isn't correct
6 Halted 0 ms 0 KB -