제출 #330607

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

joitter2

#include <bits/stdc++.h>
using namespace std;






using ll = long long;


const int maxn = 1e6 + 5;


ll nc2(ll x) {
    return x*(x-1)/2;
}

int n, q;
ll ans = 0;
int par[maxn], siz[maxn];


int parent(int x) {
    return par[x]==x?x:par[x]=parent(par[x]);
}


set<int> in[maxn]; //in[par]={node..}
set<pair<int,int>> out[maxn]; //out[par]={(par,node)..}

void join(int u, int v) {
    int x = parent(u);
    int y = parent(v);
    if (x==y) return;
    auto iter = out[y].lower_bound({x,0});
    if (iter!=out[y].end() && iter->first==x) {
	if (in[x].size()+out[x].size()<in[y].size()+out[y].size()) {
	    swap(x,y);
	}

	vector<pair<int,int>> vo;
	for (auto p: out[y]) {
	    ans -= siz[p.first];
	    in[p.first].erase(p.second);
	    if (p.first != x) vo.push_back(p);
	}

	out[y].clear();

	ans += 1ll*siz[y]*(2*siz[x] + in[x].size() - in[y].size());
	//                 internal   into x -> y    remove stuff pointing at y


	vector<int> vi;
	for (int i: in[y]) {
	    int pi = parent(i);
	    out[pi].erase({y,i});
	    if (pi != x) vi.push_back(i);
	}

	in[y].clear();


	par[y]=x;
	siz[x] += siz[y];

	for (int i: vi) join(i,x);
	for (auto p: vo) join(p.second,p.first);
	
    } else if (!in[y].count(u)) {
	ans += siz[y];
	in[y].insert(u);
	out[x].insert({y,u});
    }
}


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

    cin>>n>>q;

    for (int i=0; i<n; i++) {
	par[i]=i;
	siz[i]=1;
    }

    while (q--) {
	int u,v;
	cin>>u>>v;
	--u; --v;
	join(u,v);
	cout<<ans<<"\n";
    }
    
    
    return 0;
}

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