Submission #460743

#	Time	Username	Problem	Language	Result	Execution time	Memory
460743		kingfran1907	Pipes (CEOI15_pipes)	C++14	0 / 100	5084 ms	17524 KiB

pipes

#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("out: %d %d\n", tren.X, tren.Y);
	}
	return 0;
}

Compilation message (stderr)

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