제출 #982580

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

joitter2

#include <bits/stdc++.h>

#define ll int
#define ld long double
#define ff first
#define ss second
#define ln "\n"

using namespace std;

const ll INF = INT_MAX;

struct DSU{
	struct Vertex{
		bool cancel=0;
		set<ll> in, out, comp;
		ll size(){
			return in.size()+out.size()+comp.size();
		}
	};
	ll cnt, sz;
	vector<Vertex> a;
	vector<ll> p;
	DSU(ll N){
		a.resize(N+1);
		sz=N;
		for (ll i=1; i<=sz; i++){
			a[i].comp.insert(i);
		}
		p.resize(N+1, -1);
		cnt=0;
	}
	ll get(ll x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	void impact(ll x, ll k = 1){
		cnt+=k*(a[x].comp.size()*(a[x].comp.size()-1)+a[x].comp.size()*a[x].in.size());
	}
	void unite(ll u, ll v){
		u = get(u);
		v = get(v);
		if (u==v) return;
		if (a[u].size()<a[v].size()){
			swap(u, v);
		}
		impact(v, -1); impact(u, -1);
		for (auto ch:a[v].comp){
			a[u].comp.insert(ch);
		}
		for (auto ch:a[v].in){
			a[ch].out.erase(v);
			link(ch, u);
		}
		for (auto ch:a[v].out){
			a[ch].in.erase(v);
			link(u, ch);
		}
		impact(u);
		p[v]=u;
	}
	void link(ll u, ll v){
		ll pu = get(u), pv = get(v);
		if (pu==pv or a[u].out.count(v)) return;
		if (a[v].out.count(u)){
			unite(pu, pv);
		}else if (!a[pu].out.count(pv)){
			a[v].in.insert(u);
			a[u].out.insert(v);
			cnt++;
		}
	}
	void debug(){
		for (ll i=1; i<=sz; i++){
			cout << i << " -> " << p[i] << ": {comp: ";
			for (auto ch:a[i].comp){
				cout << ch << " ";
			}
			cout << "}, {in: ";
			for (auto ch:a[i].in){
				cout << ch << " ";
			}
			cout << "}, {out: ";
			for (auto ch:a[i].out){
				cout << ch << " ";
			}
			cout << "}\n";
		}
	}
};

void solve(){
	ll n, m; cin >> n >> m;
	DSU tree(n);
	while (m--){
		ll u, v; cin >> u >> v;
		tree.link(u, v);
		// tree.debug();
		cout << tree.cnt << endl;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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