oj.uz

Submission #269268

# Submission time Handle Problem Language Result Execution time Memory
269268 2020-08-17T06:03:42 Z 송준혁(#5099) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 7 ms 9856 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
int P[101010];
LL ans;
set<int> S[101010], T[101010];

int rt(int u){
	if (P[u] < 0) return u;
	return P[u] = rt(P[u]);
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=N; i++) P[i]=-1, S[i].insert(i);
	for (int i=1; i<=M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		int u=rt(x), v=rt(y);
		if (S[v].find(x) != S[v].end()){
			printf("%lld\n", ans);
			continue;
		}
		if (T[v].find(u) != T[v].end()){
			if (S[u].size() < S[v].size()) swap(u, v);
			ans -= P[u]*(LL)S[v].size() + P[v]*(LL)S[u].size();
			for (int t : S[v]){
				if (S[u].find(t) != S[u].end()) ans += P[u] + P[v];
				else S[u].insert(t);

				T[rt(t)].erase(v);
				T[rt(t)].insert(u);
			}
			for (int t : T[v]) T[u].insert(t);
			S[v].clear(), T[v].clear();
			P[u] += P[v], P[v]=u;
		}
		else{
			ans -= P[v];
			T[u].insert(v);
			S[v].insert(x);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Incorrect 7 ms 9856 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Incorrect 7 ms 9856 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Incorrect 7 ms 9856 KB Output isn't correct
4 Halted 0 ms 0 KB -