Submission #46925

#	Time	Username	Problem	Language	Result	Execution time	Memory
46925		HachikujiMayoi	Pipes (CEOI15_pipes)	C++14	20 / 100	5016 ms	18976 KiB

pipes

#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){
	dp[at][0] = pr;
	vis[at] = 1;
	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]){
			a = dp[a][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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10