Submission #82951

#	Time	Username	Problem	Language	Result	Execution time	Memory
82951		Saboon	Pipes (CEOI15_pipes)	C++14	100 / 100	3683 ms	14912 KiB

pipes

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
const int k = 15;

int h[maxn], par[maxn][k + 1], dp[maxn];
bool cut[maxn];

inline int lca (int v, int u) {
	if (h[v] < h[u])
		swap (v, u);
    int del = h[v] - h[u];
    while (del > 0) {
        int x = log2 (del & -del);
        del -= del & -del;
        v = par[v][x];
    }
	
	if (v == u)
		return v;
	for (int i = k; i >= 0; i--) {
		if (par[v][i] != par[u][i]) {
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

vector <int> g[maxn];

inline void dfs2 (int v, int p) {
	dp[v] = h[v];
	for (auto w : g[v]) {
		if (w != p) {
			h[w] = h[v] + 1;
			dfs2 (w, v);
		}
	}
}

inline void dfs1 (int v, int p) {
	par[v][0] = p;
	for (int i = 1; i <= k; i++) {
		if (par[v][i - 1] != -1)
			par[v][i] = par[par[v][i - 1]][i - 1];
		else if (par[v][i] != -1)
			par[v][i] = -1;
		else
		    break;
	}

	for (auto u : g[v]) {
		if (u != p) {
			dfs1 (u, v);
			if (h[v] > h[u])
				cut[u] = cut[v];
		}
	}
}

inline void dfs (int v, int p = -1) {
	for (auto w : g[v]) {
		if (w != p) {
			dfs (w, v);
			dp[v] = min (dp[v], dp[w]);
		}
	}
	cut[v] &= (h[v] <= dp[v]);
}

int dpar[maxn];
inline int get_par (int v) {
	if (dpar[v] < 0)
		return v;
	return dpar[v] = get_par (dpar[v]);
}

int n;
inline void merge (int v, int u) {
	int vpar = get_par (v);
	dfs (vpar);
	dfs1 (v, u);
	
	cut[v] = 1;
	h[v] = h[u] + 1;
	
	dfs2 (v, u);
	
	dpar[get_par(u)] += dpar[get_par(v)];
	dpar[get_par(v)] = get_par(u);
	
	g[u].PB (v);
	g[v].PB (u);
}

int main() {
	memset (par, -1, sizeof par);
	memset (dpar, -1, sizeof dpar);
	int m;
    scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		g[i].reserve (8);
	while (m --) {
		int v, u;
        scanf ("%d%d", &v, &u);
		int vpar = get_par(v), upar = get_par(u);
		if (vpar != upar) {
			if (dpar[vpar] < dpar[upar])
				swap (v, u);
			merge (v, u);
		}
		else {
			int w = lca (v, u);
			dp[v] = min (dp[v], h[w]);
			dp[u] = min (dp[u], h[w]);
		}
	}

	for (int i = 1; i <= n; i++) {
        if (dpar[i] < 0)
			dfs (i);
	}
	for (int i = 1; i <= n; i++) {
		if (cut[i]) {
		    printf ("%d %d \n", i, par[i][0]);
		}
	}
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:109:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d", &n, &m);
     ~~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:114:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d", &v, &u);
         ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10