oj.uz

답안 #474849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474849 2021-09-20T05:20:08 Z keta_tsimakuridze 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 19 ms 23800 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,q,par[N],cnt[N],sz[N], ans = 0;
map<int,int> follows[N], part[N];
vector<pair<int,pii> > edges[N];
int parent(int u) {
	return par[u] == u ? u : par[u] = parent(par[u]);
}
void merge(int u,int v) {
	u = parent(u), v = parent(v);
	if(u == v) return; 
	if(edges[u].size() < edges[v].size()) swap(u,v);
	ans -= cnt[u] * sz[u]; 
	ans -= sz[v] * cnt[v];
	cnt[u] += cnt[v];
	int f = 0;
	vector<int> x;
	for(int i = 0; i < edges[v].size(); i++) {
		int F = 0;
		int type = edges[v][i].f, a = edges[v][i].s.s, b = edges[v][i].s.f;
		if(type == 1) {
			if(parent(a) == u || part[a][u]) F = 1,cnt[u]--;
			if(follows[parent(u)][parent(a)]) F = 1, x.push_back(a);
			follows[parent(a)][u] += follows[parent(a)][v];
			part[a][u] = 1;
		}
		else {
			if(parent(a) == u) {
				F = 1;
				if(!f) cnt[u]--,f = 1;
			}
			if(follows[parent(a)][u]) F = 1, x.push_back(a);
			follows[u][parent(a)] += follows[v][parent(a)];
			part[b][parent(a)] = 1;
		}
		if(!F) edges[u].push_back(edges[v][i]);
	}
	ans += sz[u] * sz[v] * 2 + cnt[u] * (sz[u] + sz[v]);
	par[v] = u;
	sz[u] += sz[v]; 
	for(int i = 0; i < x.size(); i++)  merge(u,x[i]);
 
}
main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
	while(q--) {
		int u,v;
		cin >> u >> v;
		if(parent(u) == parent(v) || part[u][parent(v)]) {
			cout << ans <<"\n";
			continue;
		}		
		if(follows[parent(v)][parent(u)]) {
			merge(u,v);
		}
		else if(!part[u][parent(v)]){ 
			follows[parent(u)][parent(v)] = 1;
			part[u][parent(v)] = 1;
			edges[parent(u)].push_back({0,{u,v}});
			edges[parent(v)].push_back({1,{v,u}});
			ans += sz[parent(v)];
			cnt[parent(v)]++;
		}
		cout << ans << "\n";
	}
	
 }

Compilation message

joitter2.cpp: In function 'void merge(long long int, long long int)':
joitter2.cpp:23:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 0; i < edges[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
joitter2.cpp:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < x.size(); i++)  merge(u,x[i]);
      |                 ~~^~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 14 ms 23800 KB Output is correct
4 Correct 14 ms 23760 KB Output is correct
5 Correct 14 ms 23708 KB Output is correct
6 Correct 14 ms 23724 KB Output is correct
7 Incorrect 19 ms 23756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 14 ms 23800 KB Output is correct
4 Correct 14 ms 23760 KB Output is correct
5 Correct 14 ms 23708 KB Output is correct
6 Correct 14 ms 23724 KB Output is correct
7 Incorrect 19 ms 23756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23800 KB Output is correct
3 Correct 14 ms 23800 KB Output is correct
4 Correct 14 ms 23760 KB Output is correct
5 Correct 14 ms 23708 KB Output is correct
6 Correct 14 ms 23724 KB Output is correct
7 Incorrect 19 ms 23756 KB Output isn't correct
8 Halted 0 ms 0 KB -