oj.uz

답안 #1020081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020081 2024-07-11T13:59:36 Z Gray 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 344 KB 
#include <ios>
#include<iostream>
#include <queue>
#include <set>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ull unsigned ll
#define ln "\n"
#define pll pair<ll, ll>

using namespace std;

struct DSU{
	vector<ll> p;
	vector<multiset<ll>> in, out, mem;
	queue<pair<ll, ll>> links;
	ll pedge;
	DSU(ll N){
		p.resize(N+1, -1);
		in.resize(N+1);
		out.resize(N+1);
		mem.resize(N+1);
		for (ll i=1; i<=N; i++) mem[i].insert(i);
		pedge=0;
	}
	ll get(ll x){
		return p[x]==-1?x:p[x]=get(p[x]);
	}
	void unite(ll u, ll v){
		if (in[u].size()+out[u].size()+mem[u].size()<in[v].size()+out[v].size()+mem[v].size()) swap(u, v);
		// cout << "Unity: " << u << " " << v << ln;
		// cout << "Pre: " << pedge << ln;
		p[v]=u;
		pedge+=mem[u].size()*mem[v].size()*2+in[u].size()*mem[v].size();
		for (auto ind:in[v]){
			pedge-=mem[v].size();
			out[ind].erase(out[ind].find(v));
			link(ind, u);
		}
		in[v].clear();
		for (auto outd:out[v]){
			pedge-=mem[outd].size();
			in[outd].erase(in[outd].find(v));
			link(outd, u);
		}
		out[v].clear();
		for (auto child:mem[v]){
			mem[u].insert(child);
		}
		mem[v].clear();
		// cout << "Post: " << pedge << ln;

	}
	void follow(ll u, ll v){
		link(u, v);
		while (!links.empty()){
			unite(links.front().ff, links.front().ss);
			links.pop();
		}
		// cout << "end\n";
	}
	void link(ll u, ll v){
		// cout << "Linking: " << u << " - " << v << ln;
		u=get(u);
		v=get(v);
		if (out[u].find(v)!=out[u].end()) return;
		if (u==v) return;
		if (out[v].find(u)!=out[v].end()){
			pedge-=mem[u].size()*out[v].count(u);
			out[v].erase(u);
			in[u].erase(v);
			links.push({u, v});
			return;
		}else{
			pedge+=mem[v].size();
			out[u].insert(v);
			in[v].insert(u);
		}
	}
};

void solve(){
	ll n, m; cin >> n >> m;
	DSU tr(n);
	for (ll i=0; i<m; i++){
		ll u, v; cin >> u >> v;
		tr.follow(u, v);
		cout << tr.pedge << ln;
	}
}

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -