oj.uz

Submission #527196

# Submission time Handle Problem Language Result Execution time Memory
527196 2022-02-17T03:29:25 Z maomao90 Pipes (CEOI15_pipes) C++17
100 / 100
 2844 ms 9220 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template<class T>
inline bool mxto(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T>
inline bool mnto(T &a, T b) {return a > b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
#define MP make_pair
typedef pair<int, int> ii;
#define pb push_back
#define ALL(x) x.begin(), x.end()
typedef vector<int> vi;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 100005

int n, m;
vi adj[MAXN];

int uf[MAXN], rnk[MAXN];
void init() {
	REP (i, 0, MAXN) {
		uf[i] = i;
		rnk[i] = 0;
	}
}
int findp(int u) {
	if (uf[u] == u) return u;
	return uf[u] = findp(uf[u]);
}
bool join(int a, int b) {
	int pa = findp(a), pb = findp(b);
	if (pa == pb) return 0;
	if (rnk[pa] < rnk[pb]) swap(pa, pb);
	if (rnk[pa] == rnk[pb]) rnk[pa]++;
	uf[pb] = pa;
	return 1;
}

bool vis[MAXN];
int p[MAXN];
int dfs(int u) {
	int st = 1, mx = -1, mxid = -1;
	REP (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (vis[v]) continue;
		p[v] = u;
		vis[v] = 1;
		int tmp = dfs(v);
		if (mxto(mx, tmp)) {
			mxid = i;
		}
		st += tmp;
	}
	if (mxid != -1) {
		swap(adj[u][0], adj[u][mxid]);
	}
	return st;
}

int pre[MAXN], head[MAXN], ptr;
int mppre[MAXN];
void hld(int u, int ch) {
	//cerr << u << '\n';
	head[u] = ch;
	pre[u] = ptr++;
	mppre[pre[u]] = u;
	if (adj[u].empty()) return;
	if (adj[u][0] != p[u]) {
		hld(adj[u][0], ch);
	}
	REP (i, 1, adj[u].size()) {
		int v = adj[u][i];
		if (p[u] == v) continue;
		hld(v, v);
	}
}

int psm[MAXN];
void incre(int l, int r) {
	assert(l <= r);
	psm[l]++;
	psm[r + 1]--;
}

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n >> m;
	init();
	REP (i, 0, m) {
		int u, v; cin >> u >> v;
		if (join(u, v)) {
			cerr << u << " --- " << v << '\n';
			adj[u].pb(v);
			adj[v].pb(u);
		}
	}
	REP (i, 1, n + 1) {
		if (vis[i]) continue;
		vis[i] = 1;
		p[i] = -1;
		dfs(i);
		hld(i, i);
	}
	init();
	cin.seekg(0, cin.beg);
	cin >> n >> m;
	// head has smallest pre
	REP (i, 0, m) {
		int a, b; cin >> a >> b;
		cerr << ' ' << a << ' ' << b << '\n';
		if (join(a, b)) {
			continue;
		}
		while (head[a] != head[b]) {
			if (pre[head[a]] < pre[head[b]]) swap(a, b);
			incre(pre[head[a]], pre[a]);
			a = p[head[a]];
		}
		if (a != b) {
			if (pre[a] < pre[b]) swap(a, b);
			incre(pre[b] + 1, pre[a]);
		}
	}
	REP (i, 0, n) {
		if (i) psm[i] += psm[i - 1];
		if (p[mppre[i]] == -1 || psm[i] > 0) continue;
		cout << mppre[i] << ' ' << p[mppre[i]] << '\n';
	}
	return 0;
}

/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/

Compilation message

pipes.cpp: In function 'int dfs(int)':
pipes.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   57 |  REP (i, 0, adj[u].size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
pipes.cpp:57:2: note: in expansion of macro 'REP'
   57 |  REP (i, 0, adj[u].size()) {
      |  ^~~
pipes.cpp: In function 'void hld(int, int)':
pipes.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   85 |  REP (i, 1, adj[u].size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
pipes.cpp:85:2: note: in expansion of macro 'REP'
   85 |  REP (i, 1, adj[u].size()) {
      |  ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3788 KB Output is correct
2 Correct 7 ms 3696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 4712 KB Output is correct
2 Correct 182 ms 4648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 5008 KB Output is correct
2 Correct 371 ms 4708 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 5588 KB Output is correct
2 Correct 504 ms 5508 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 7344 KB Output is correct
2 Correct 677 ms 7340 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1303 ms 7992 KB Output is correct
2 Correct 1227 ms 7920 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1742 ms 8884 KB Output is correct
2 Correct 1622 ms 8904 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2210 ms 9028 KB Output is correct
2 Correct 1994 ms 9192 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2844 ms 8708 KB Output is correct
2 Correct 2556 ms 9220 KB Output is correct