Submission #235425

#	Time	Username	Problem	Language	Result	Execution time	Memory
235425		rajarshi_basu	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	5 ms	512 KiB

joitter2

#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define mp make_pair
#define vv vector
#define endl '\n'

using namespace std;
const int MAXN = 1e3+5;
int D = 0;
int E = 0;
int F = 0;
int G = 0;
struct DSU{
	ll tot = 0;
	int parent[MAXN];
	set<int> incoming[MAXN];// individual nodes 
	set<int> incomingCliques[MAXN];
	set<int> sentTo[MAXN];
	set<int> allNodes[MAXN];
	ll sz[MAXN];
	bool paCleared;
	DSU(){
		FOR(i,MAXN)parent[i] = i;
		FOR(i,MAXN)sz[i] = 1;
		FOR(i,MAXN)allNodes[i].insert(i);
	}
	int find(int a){
		if(a != parent[a])parent[a] = find(parent[a]);
		return parent[a];
	}
	bool isSame(int a,int b){
		return find(a) == find(b);
	}
	// outgoing[e] = {a,i} means there are i edges going from Supernodes e to a
	// we only keep track of outgoing edges + internal clique edges;
	
	queue<ii> q;
	inline void addEdge(int a,int b){
		b = find(b);
		incomingCliques[b].insert(find(a));
		incoming[b].insert(a);
		sentTo[find(a)].insert(b);
		tot += sz[b];
	}

	void makeParent(int pa,int pb,set<int>& allIncomers, set<int>& sss){
		// make pa parent
		/*
		for(auto e : incoming[pa]){
			if(find(e) != pb)
				allIncomers.insert(e);
			tot -= sz[pa];
		}
		*/
		incomingCliques[pa].erase(pb);
		tot -= (incoming[pa].size())*sz[pa];
		for(auto e: allNodes[pb]){
			if(incoming[pa].find(e) != incoming[pa].end()){
				incoming[pa].erase(e);
			}
		}
		


		for(auto e : incoming[pb]){
			if(find(e) != pa){
				allIncomers.insert(e);
				if(incoming[pa].find(e) != incoming[pa].end()){
					incoming[pa].erase(e);
					
				}
			}
			
			tot -=sz[pb];
		}
		tot += ((ll)incoming[pa].size()) * (sz[pb]+sz[pa]);
		//for(auto x: allNodes[pb]){
		vi lst;
		for(auto e : sentTo[pb]){
			if(find(e) == pa){
				lst.pb(e);
				continue;
			}
			sss.insert(find(e));
			incomingCliques[e].erase(pb);
			incomingCliques[e].insert(pa);
		}
		for(auto e: lst)sentTo[pb].erase(e);
		
		//incoming[pa].clear();
		incoming[pb].clear();
		//incomingCliques[pa].clear();
		incomingCliques[pb].clear();
		//sentTo[pa].clear();
		sentTo[pb].clear();
	}


	void merge(int a,int b){

		int pa = find(a);
		int pb = find(b);
		tot += 2*sz[pa]*sz[pb]; // new internal edges of the clique.
		//allIncomers.clear();
		//cout << "COMBINING: " << pa << " " << pb << endl;
		if(sz[pa] < sz[pb])swap(pa,pb);

		for(auto x : sentTo[pb])sentTo[pa].insert(x);
		for(auto x : allNodes[pb])allNodes[pa].insert(x);


		set<int> allIncomers;
		set<int> sss;
		makeParent(pa,pb,allIncomers,sss);
		parent[pb] = pa;
		sz[pa] += sz[pb];
	
		for(auto e : sss){
			handleEdge(pa,e);
		}
		for(auto e : allIncomers){
			handleEdge(e,pa);
		}

	}

	void handleEdge(int a,int b){
		//cout <<a << " " << b << endl;
		int pa = find(a);
		int pb = find(b);

		//cout << "We have to handle " << a+1 << " : " << b+1 << endl;
		if(pa == pb)return;
		// edge is a-> b
		if(incoming[pb].find(a) != incoming[pb].end())return;
		//cout << "We do have to solve it" << a+1 << " : " << b+1 << endl;
		if(incomingCliques[pa].find(pb) != incomingCliques[pa].end()){
			merge(a,b);
		}else{
			addEdge(a,b);
		}
	}
};	

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin >> n >> m;
	DSU dsu;
	FOR(i,m){
		dsu.paCleared = false;
		int a,b;
		cin >> a >> b;
		a--;b--;
		dsu.q.push({a,b});
		while(!dsu.q.empty()){
			auto x = dsu.q.front();dsu.q.pop();
			dsu.handleEdge(x.ff,x.ss);
		}
		cout << dsu.tot << endl;
	}
	return 0;
}

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