oj.uz

답안 #682052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682052 2023-01-15T12:45:35 Z Makarooni Mergers (JOI19_mergers) C++17
0 / 100
 12 ms 23764 KB 
/* 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.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

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