oj.uz

답안 #856526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856526 2023-10-03T18:58:25 Z serifefedartar 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 5724 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;
set<int> in[MAXN];
int par[MAXN], sz[MAXN];
queue<pair<int,int>> q;
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 ;
	if (graph[x].size() + rev[x].size() + in[x].size() < graph[y].size() + rev[y].size() + in[y].size())
		swap(x, y);

	ans += in[y].size() * sz[x] + in[x].size() * sz[y]; 
	sz[x] += sz[y];
	par[y] = x;

	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;
	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 1 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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