oj.uz

답안 #856835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856835 2023-10-04T17:12:42 Z serifefedartar 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 2 ms 5980 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 1e5 + 5;
 
vector<set<int>> graph, rev;
queue<pair<int,int>> q;
set<int> in[MAXN];
int par[MAXN];
ll sz[MAXN];
ll ans = 0;
int find(int node) {
	if (par[node] == node)
		return node;
	return par[node] = find(par[node]);
}
 
void conn(int from, int to) {
	graph[from].insert(to);
	rev[to].insert(from);
	if (graph[to].count(from))
		q.push({from, to});	
}
 
void merge(int x, int y) {
	if (x == y)
		return ;
	bool swapped = false;
	if (graph[x].size() + rev[x].size() + in[x].size() < graph[y].size() + rev[y].size() + in[y].size()) {
		swap(x, y);
		swapped = true;
	}
 
	ans += in[y].size() * sz[x] + in[x].size() * sz[y]; 
	sz[x] += sz[y];
	par[y] = x;
 		
 	if (swapped)
 		swap(x, y);
	for (auto u : in[y]) {
		if (in[x].count(u) == 0)
			in[x].insert(u);
		else
			ans -= sz[x];
	}
 
	graph[x].erase(y);
	graph[y].erase(x);
	rev[x].erase(y); 
	rev[y].erase(x);
	for (auto u : graph[y]) {
		rev[u].erase(y);
		conn(x, u); 
	}
	for (auto u : rev[y]) {
		graph[u].erase(y);
		conn(u, x);
	}
}
 
int main() {
	fast
	int N, M, a, b;
	cin >> N >> M;
 
	for (int i = 1; i <= N; i++) {
		par[i] = i, sz[i] = 1;
		in[i].insert(i);
	}
	graph = vector<set<int>>(N+1, set<int>());
	rev = vector<set<int>>(N+1, set<int>());
 
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		int par_a = find(a);
		int par_b = find(b);
 
		if (par_b == par_a)
			continue;
		if (in[par_b].count(a) == 0) {
			in[par_b].insert(a);
			ans += sz[par_b];
 
			conn(par_a, par_b);
			while (!q.empty()) {
				int from = q.front().f;
				int to = q.front().s;
				q.pop();
				merge(find(from), find(to));
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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