Submission #377181

#	Time	Username	Problem	Language	Result	Execution time	Memory
377181		nafis_shifat	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	17 / 100	1635 ms	125812 KiB

joitter2

#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];
set<int> ireps[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];
					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 if(ireps[V].count(x)) {
					sz2[U][1]--;
					reps[x].erase(U);
					eds[x][0].erase(i);
					sz2[X][0]--;
					it2 = eds[i][1].erase(it2);
					ans -= sz[U];
				} else it2++;
			}

		}


		while(!ireps[U].empty()) {
			auto it = ireps[U].begin();
			ireps[V].insert(*it);
			reps[*it].erase(U);
			reps[*it].insert(V);
			ireps[U].erase(it);
		}
		
	

		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 {
	    if(reps[u].count(V)) return;
	    
		ans += sz[V];
		eds[u][0].insert(v);
		eds[v][1].insert(u);
		
		adj[U].insert(V);
		in[V].insert(U);
		
		reps[u].insert(V);
		ireps[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 (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 0 / 83