제출 #682052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682052		Makarooni	Mergers (JOI19_mergers)	C++17	0 / 100	12 ms	23764 KiB

mergers

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

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

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 10;
const ll MOD = 1e9 + 7;
const ll inf = 2e17;
const ll INF = 7e15;

set<int> g[N], g2[N], g3[N];
int par[N], Sz[N];
map<int, int> mp[N];
set<int> st[N];

int gp(int v){
	if(par[v] == v)
		return v;
	return par[v] = gp(par[v]);
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	if(n > 50)
		return 0;
	for(int i = 1; i <= n; i++){
		par[i] = i;
		st[i].insert(i);
		Sz[i] = 1;
	}
	int u, v, ans = 0;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		int x = gp(u), y = gp(v);
		if(x == y){
			cout << ans << endl;
			continue;
		}
		g[x].insert(y);
		g2[y].insert(u);
		if(g[y].find(x) != g[y].end()){
			g3[u].insert(y);
			ans -= Sz[x] * (Sz[x] - 1);
			ans -= Sz[y] * (Sz[y] - 1);
			ans -= mp[x][y] * Sz[y];
			ans -= mp[y][x] * Sz[x];
			ans += (Sz[x] + Sz[y]) * (Sz[x] + Sz[y] - 1);
			if(Sz[x] > Sz[y]){
				swap(x, y);
				swap(u, v);
			}
			for(int w : st[x]){
				g2[y].erase(w);
			}
			for(int w : st[y])
				g2[x].erase(w);
			int t = 0;
			for(int w : g2[x]){  // oonayee ke be X yal khooroji daran
				if(g2[y].find(w) != g2[y].end())
					t++;
				mp[gp(w)][y]++;
				g[gp(w)].insert(y);
				g3[w].insert(y);
			}
			//cout << "ajab " << x << " " << y << " " << *g2[x].begin() << " " << *g2[y].begin() << endl;
			ans += (sz(g2[x]) - t) * Sz[y];
			ans += (sz(g2[y]) - t) * Sz[x];
			for(int w : g2[x])
				g2[y].insert(w);
			//cout << "wef " << sz(g2[x]) << " " << sz(g2[y]) << endl;
			for(int w : st[x]){
				st[y].insert(w);
				Sz[y]++;
			}
			for(int w : g[x]){
				if(gp(w) == y)
					continue;
				mp[y][gp(w)] += mp[x][gp(w)];
				g[y].insert(w);
			}
			par[x] = y;
		}
		else{
			if(g3[u].find(y) != g3[u].end()){
				cout << ans << endl;
				continue;
			}
			mp[x][y]++;
			g3[u].insert(y);
			g2[y].insert(u);
			ans += Sz[y];
		}
		cout << ans << endl;
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30