oj.uz

Submission #46927

# Submission time Handle Problem Language Result Execution time Memory
46927 2018-04-24T20:09:33 Z HachikujiMayoi Pipes (CEOI15_pipes) C++14
70 / 100
 5000 ms 18976 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, m;
int dep[N], par[N], dp[N][18], S[N], vis[N];
vector <int> g[N];
set <int> blocked;

int Get(int a){
	if(par[a] == a) return a;
	return par[a] = Get(par[a]);
}

void dfs(int at, int pr){
	vis[at] = 1;
	dp[at][0] = pr;
	for(int i = 1; i <= 17; ++i) dp[at][i] = dp[ dp[at][i - 1] ][ i - 1 ];
	for(auto i : g[at]){
		if(i == pr) continue;
		dep[i] = dep[at] + 1;
		dfs(i, at);
	}
}

int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	for(int i = 17; i >= 0; --i){
		if(dep[b] - (1 << i) >= dep[a]){
			b = dp[b][i];
		}
	}
	if(a == b) return a;
	for(int i = 17; i >= 0; --i){
		if(dp[a][i] != dp[b][i]){
			a = dp[a][i];
			b = dp[b][i];
		}
	}
	return dp[a][0];
}

void solve(int at, int pr){
	vis[at] = 1;
	for(auto i : g[at]){
		if(i == pr) continue;
		solve(i, at);
		S[at] += S[i];
	}
	if(S[at] == 0 && pr){
		printf("%d %d\n", at, pr);
	}
}

int main(){
	int x, y;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i) par[i] = i;
	for(int i = 1; i <= m; ++i){
		scanf("%d %d", &x, &y);
		if(Get(x) == Get(y)) continue;
		g[x].push_back(y);
		g[y].push_back(x);
		x = Get(x);
		y = Get(y);
		par[x] = y;
		blocked.insert(i);
	}
	for(int i = 1; i <= n; ++i){
		if(!vis[i]){
			dfs(i, 0);
		}
	}
	rewind(stdin);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d %d", &x, &y);
		if(blocked.find(i) != blocked.end()) continue;
		int lc = lca(x, y);
		S[lc] -= 2;
		S[x] += 1;
		S[y] += 1;
	}
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; ++i){
		if(!vis[i]){
			solve(i, 0);
		}
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3812 KB Output is correct
2 Correct 12 ms 3712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 3572 KB Output is correct
2 Correct 295 ms 3576 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 4652 KB Output is correct
2 Correct 678 ms 4520 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 6904 KB Output is correct
2 Correct 824 ms 7800 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 14200 KB Output is correct
2 Correct 1332 ms 14200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2391 ms 15920 KB Output is correct
2 Correct 2172 ms 15788 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3758 ms 18976 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4376 ms 18976 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 18176 KB Time limit exceeded
2 Halted 0 ms 0 KB -