제출 #212204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212204		nvmdava	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	2086 ms	64888 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 100005
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

int p[N], sz[N];
int find(int v){
	return v == p[v] ? v : p[v] = find(p[v]);
}

ll res = 0;

multiset<pair<int, int> > on, in[N], con;
int cnt[N];

void insert(int v, int u){
	int vv = find(v);
	int uu = find(u);
	if(vv == uu) return;
	if(on.count({v, uu})) return;

	if(!con.count({uu, vv})){
		res += sz[uu];
		con.insert({vv, uu});
		on.insert({v, uu});
		++cnt[uu];
		in[vv].insert({v, uu});
		in[uu].insert({v, uu});
		return;
	}
	
	if(in[vv].size() < in[uu].size())
		swap(vv, uu);

	res -= 1LL * sz[vv] * (sz[vv] - 1);
	res -= 1LL * sz[uu] * (sz[uu] - 1);

	for(auto x : in[uu]){
		res -= sz[x.ss];
		con.erase(con.find({find(x.ff), x.ss}));
		on.erase(x);
		--cnt[x.ss];
		if(x.ss == uu)
			in[find(x.ff)].erase(x);
		else
			in[x.ss].erase(x);
	}

	p[uu] = vv;
	res += cnt[vv] * sz[uu];
	sz[vv] += sz[uu];
	res += 1LL * sz[vv] * (sz[vv] - 1);

	for(auto x : in[uu])
		insert(x.ff, x.ss);
	
	in[uu].clear();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
    	p[i] = i;
    	sz[i] = 1;
    }
    while(m--){
    	int v, u;
    	cin>>v>>u;
    	insert(v, u);
    	cout<<res<<'\n';
    }
}

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