oj.uz

답안 #377039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377039 2021-03-12T20:41:52 Z nafis_shifat 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 18 ms 26220 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;


int parent[mxn];
int sz[mxn];


set<int> adj[mxn];
set<int> in[mxn];
vector<int> nodes[mxn];

int sz2[mxn][2];
set<int> eds[mxn][2];

set<int> reps[mxn];




ll ans = 0;


int findrep(int u) {
	return parent[u] == u ? u : parent[u] = findrep(parent[u]);
}
void unite(int u,int v) {
	int U = findrep(u);
	int V = findrep(v);
	if(U == V) return;

	if(adj[V].count(U)) {
		ans += 2 * sz[U] * sz[V];
		if(sz[U] + sz2[U][0] + sz2[U][1] > sz[V] + sz2[V][0] + sz2[V][1]) swap(U,V);
		vector<int> nod1,nod2;
		for(int i : nodes[U]) {
		
			auto it1 = eds[i][0].begin();
			while(it1 != eds[i][0].end()) {
				int x = *it1;
				int X = findrep(x);

				if(X == V) {
					ans -= sz[V];

					in[V].erase(U);
					adj[U].erase(V);

					eds[x][1].erase(i);
					sz2[X][1]--;
					it1 = eds[i][0].erase(it1);
					sz2[U][0]--;
				} else if(in[V].count(X)) {
					nod1.push_back(X);
					in[X].erase(U);
					eds[x][1].erase(i);
					sz2[X][1]--;
					ans -= sz[X];
					it1 = eds[i][0].erase(it1);
					sz2[U][0]--;

				} else it1++;
			}



			auto it2 = eds[i][1].begin();
			while(it2 != eds[i][1].end()) {
				int x = *it2;
				int X = findrep(x);

				if(X == V) {
					ans -= sz[U];
 					//cout<<"HERE"<<ans<<endl;

					adj[V].erase(U);
					in[U].erase(V);

					eds[x][0].erase(i);
					sz2[X][0]--;
					it2 = eds[i][1].erase(it2);
					sz2[U][1]--;
				} else if(adj[V].count(X)) {
					nod2.push_back(X);
					adj[X].erase(U);
					eds[x][0].erase(i);
					sz2[X][0]--;
					ans -= sz[U];
					it2 = eds[i][1].erase(it2);
					sz2[U][1]--;
				} else it2++; 
			}

		}
		
	

		ans += sz2[U][1] * sz[V];
		ans += sz2[V][1] * sz[U];


		parent[U] = V;
		sz[V] += sz[U];
		sz2[V][0] += sz2[U][0];
		sz2[V][1] += sz2[U][1];

		while(!nodes[U].empty()) {
			int x = nodes[U].back();
			nodes[U].pop_back();
			nodes[V].push_back(x);
		}



		while(!adj[U].empty()) {
			int x = *adj[U].begin();
			in[x].erase(U);
			adj[U].erase(x);
			adj[V].insert(x);
			in[x].insert(V);
		}

		while(!in[U].empty()) {
			int x = *in[U].begin();
			in[U].erase(x);
			adj[x].erase(U);
			in[V].insert(x);
			adj[x].insert(V);
		}
		

		for(int x : nod1) {
			unite(V,x);
		}
		for(int x : nod2) {
			unite(x,V);
		}

	} else {
	    for(int i : nodes[V]) {
	        if(eds[u][0].count(i)) return;
	    }
		ans += sz[V];
		eds[u][0].insert(v);
		eds[v][1].insert(u);
		
		adj[U].insert(V);
		in[V].insert(U);
		
		sz2[U][0]++;
		sz2[V][1]++;
	}
}


int main() {
	int n,m;
	cin >> n >> m;

	for(int i = 1; i <= n; i++) {
		parent[i] = i;
		sz[i] = 1;
		sz2[i][0] = sz2[i][1] = 0;
		nodes[i].push_back(i);
	}


	for(int i = 1; i <= m; i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		unite(u,v);

		cout<<ans<<endl;
	}
	
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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