Submission #734044

#	Time	Username	Problem	Language	Result	Execution time	Memory
734044		lukameladze	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	974 ms	114064 KiB

joitter2

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,a[N],p[N],m;
long long ans, sz[N];
set <int> g[N], rg[N],v[N],comp[N];
int get(int sz) {
	return sz * (sz - 1);
}
int get_col(int a) {
	if (a == p[a]) return a;
	else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
	a = get_col(a); b = get_col(b);
	if (a == b) return ;
	if (comp[a].size() < comp[b].size()) swap(a,b); 
	ans -= get(sz[a]);
	ans -= get(sz[b]);
	
	ans -= v[a].size() * sz[a];
	ans -= v[b].size() * sz[b];
	ans += get(sz[a] + sz[b]);
	

	for (int x : v[b]) {
		if (get_col(x) != a) v[a].insert(x); 
	}
	for (int x : comp[b]) {
		if (v[a].count(x)) {
			v[a].erase(x);
		}
		comp[a].insert(x); p[x] = a;
	}
	comp[b].clear();
	ans += v[a].size() * (sz[a] + sz[b]);
	v[b].clear();
	p[b] = a;
	sz[a] += sz[b]; sz[b] = 0;
	vector <pii> vec;
	for (int to : g[b]) {
		rg[to].erase(b); if (get_col(to) != a) { rg[to].insert(a), g[a].insert(to); if (g[to].count(a)) vec.pb({to, a}); }
	}
	for (int to : rg[b]) {
		g[to].erase(b); if (get_col(to) != a) { g[to].insert(a), rg[a].insert(to); if (g[a].count(to)) vec.pb({to, a}); }
	}
	for (pii sth : vec) {
		col(sth.f, sth.s);
	}
	/*
	while (s[x].lower_bound({y, 0}) != s[x].end()){ 
		pii sth = *s[x].lowesr_bound({y, 0});
		if (sth.f != y) break;
		s[x].erase(sth);
	}
	while (s[y].lower_bound({x, 0}) != s[y].end()) {
		pii sth = *s[y].lower_bound({x, 0});
		if (sth.f != x) break;
		s[y].erase(sth);
	}
	*/
	
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
  	
	for (int i = 1; i <= n; i++) {
		p[i] = i; sz[i] = 1; comp[i].insert(i);
	}
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin>>a>>b;
		int x = get_col(a), y = get_col(b);
		if (x == y) {
			 cout<<ans<<'\n';
			continue;
		}
		if (v[y].count(a)) {
			 cout<<ans<<'\n';
			continue;
		}
		g[x].insert(y); rg[y].insert(x); v[y].insert(a);
		ans += sz[y];
		if (g[x].count(y) && g[y].count(x)) {
			col(x, y);
		} 
		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

joitter2.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~

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