oj.uz

답안 #460762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
460762 2021-08-09T09:16:04 Z kingfran1907 Pipes (CEOI15_pipes) C++14
40 / 100
 5000 ms 18400 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< pair<int, bool> > graph[maxn];
vector< int > ops[maxn];
int parr[maxn], siz[maxn];
int dp[20][maxn];
int wh[maxn], dep[maxn];
bool bio[maxn];

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 < 19; i++) dp[i][x] = dp[i - 1][dp[i - 1][x]];
	for (auto tren : graph[x]) {
		if (tren.X != parr) recal(tren.X, x);
	}
}

int lif(int x, int val) {
	for (int i = 0; i < 19; 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 = 18; 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 i = 0; i < graph[x].size(); i++) {
		auto &tren = graph[x][i];
		if (tren.X == par) continue;
		
		int kol = dfs(tren.X, x);
		//printf("returned %d --> %d\n", tren, kol);
		if (kol > 0) {
			tren.Y = false;
			int ind = ops[x][i];
			graph[tren.X][ind].Y = false;
		}
		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);
			
			ops[a].push_back(graph[b].size()); 
			ops[b].push_back(graph[a].size());
			graph[a].push_back(make_pair(b, true));
			graph[b].push_back(make_pair(a, true));
		} 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 (int i = 1; i <= n; i++) {
		for (auto tren : graph[i]) {
			if (tren.Y && i < tren.X) printf("%d %d\n", i, tren.X);
		}
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int dfs(int, int)':
pipes.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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