oj.uz

답안 #220437

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220437 2020-04-08T00:21:42 Z super_j6 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 10 ms 9728 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 100000;
int n, m;
int par[maxn];
long long sz[maxn];
set<int> ei[maxn];
set<pi> eo[maxn];
long long ret;

int find(int x){
	return x == par[x] ? x : par[x] = find(par[x]);
}

void solve(int u, int v){
	int x = find(u), y = find(v);
	if(x == y) return;
	auto it = eo[y].lower_bound({x, 0});
	if(it != eo[y].end() && (*it).f == x){
		ret += 2 * sz[x] * sz[y] + sz[y] * (ei[x].size() - ei[y].size());
		if(ei[x].size() + eo[x].size() < ei[y].size() + eo[y].size()) swap(x, y);
		vector<int> vi;
		for(int i : ei[y]){
			int j = find(i);
			eo[j].erase({y, i});
			if(j != x) vi.push_back(i);
		}
		ei[y].clear();
		vector<pi> vo;
		for(pi i : eo[y]){
			ret -= sz[i.f];
			ei[i.f].erase(i.s);
			if(i.f != x) vo.push_back(i);
		}
		eo[y].clear();
		par[y] = x, sz[x] += sz[y];
		for(int i : vi) solve(i, x);
		for(pi i : vo) solve(i.s, i.f);
	}else if(!ei[y].count(u)){
		ret += sz[y];
		ei[y].insert(x);
		eo[x].insert({y, u});
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++) par[i] = i, sz[i] = 1;
	for(int i = 0; i < m; i++){
		int u, v;
		cin >> u >> v;
		solve(u, v);
		cout << ret << endl;
	}

	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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