oj.uz

답안 #460745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
460745 2021-08-09T09:05:35 Z kingfran1907 Pipes (CEOI15_pipes) C++14
40 / 100
 5000 ms 16792 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
vector< int > graph[maxn];
int parr[maxn], siz[maxn];
int dp[20][maxn];
int wh[maxn], dep[maxn];
bool bio[maxn];
set< pair<int, int> > ans;

int fin(int x) {
	if (parr[x] == x) return x;
	return parr[x] = fin(parr[x]);
} 

void merg(int x, int y) {
	x = fin(x);
	y = fin(y);
	
	if (x == y) return;
	parr[y] = x, siz[x] += siz[y];
}

void recal(int x, int parr) {
	//printf("recalculating %d %d\n", x, parr);
	dp[0][x] = parr;
	dep[x] = 1 + dep[parr];
	bio[x] = false, wh[x] = 0;
	for (int i = 1; i < 20; i++) dp[i][x] = dp[i - 1][dp[i - 1][x]];
	for (int tren : graph[x]) {
		if (tren != parr) recal(tren, x);
	}
}

int lif(int x, int val) {
	for (int i = 0; i < 20; i++) {
		if (val & (1 << i)) x = dp[i][x];
	}
	return x;
}

int lca(int x, int y) {
	if (dep[x] > dep[y]) x = lif(x, dep[x] - dep[y]);
	else y = lif(y, dep[y] - dep[x]);
	if (x == y) return x;
	
	for (int i = 19; i >= 0; i--) {
		if (dp[i][x] != dp[i][y]) x = dp[i][x], y = dp[i][y];
	}
	return dp[0][x];
}

int dfs(int x, int par) {
	int out = wh[x];
	bio[x] = true;
	//printf("dfs %d %d\n", x, par);
	for (int tren : graph[x]) {
		if (tren == par) continue;
		
		int kol = dfs(tren, x);
		//printf("returned %d --> %d\n", tren, kol);
		if (kol > 0) {
			pair<int, int> tr = {x, tren};
			if (tr.X > tr.Y) swap(tr.X, tr.Y);
			ans.erase(tr);
		}
		out = max(out, kol - 1);
	}
	return out;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) parr[i] = i, siz[i] = dep[i] = 1;
	memset(bio, false, sizeof bio);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		
		if (fin(a) != fin(b)) {
			//printf("edge: %d %d\n", a, b);
			if (siz[fin(a)] > siz[fin(b)]) swap(a, b);
			
			//printf("root parr: %d (%d)\n", dp[0][fin(b)], fin(b));
			//assert(dp[0][fin(b)] == 0);
			dfs(fin(b), 0);
			recal(b, a);
			merg(a, b);
			
			graph[a].push_back(b);
			graph[b].push_back(a);
			
			pair<int, int> tr = {a, b};
			if (tr.X > tr.Y) swap(tr.X, tr.Y);
			ans.insert(tr);
		} else {
			int lc = lca(a, b);
			wh[a] = max(wh[a], dep[a] - dep[lc]);
			wh[b] = max(wh[b], dep[b] - dep[lc]);
		}
	}
	
	for (int i = 1; i <= n; i++) {
		int x = fin(i);
		if (!bio[x]) dfs(x, 0);
	}
	
	for (auto tren : ans) {
		printf("%d %d\n", tren.X, tren.Y);
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 662 ms 3504 KB Output is correct
2 Correct 261 ms 3584 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 3344 KB Output is correct
2 Correct 268 ms 3344 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3923 ms 4220 KB Output is correct
2 Correct 1027 ms 4348 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5090 ms 6204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5098 ms 12692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5068 ms 13972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5059 ms 16792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 16668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5079 ms 16024 KB Time limit exceeded
2 Halted 0 ms 0 KB -