oj.uz

Submission #527178

# Submission time Handle Problem Language Result Execution time Memory
527178 2022-02-17T03:16:06 Z maomao90 Pipes (CEOI15_pipes) C++17
30 / 100
 1331 ms 65540 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];
vii qry;

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;
}

int vis[MAXN], p[MAXN], lvl[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;
		lvl[v] = lvl[u] + 1;
		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)) {
			qry.pb(MP(u, v));
		} else {
			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);
	}
	// head has smallest pre
	for (auto [a, b] : qry) {
		while (head[a] != head[b]) {
			if (lvl[head[a]] < lvl[head[b]]) swap(a, b);
			incre(pre[head[a]], pre[a]);
			a = p[head[a]];
		}
		if (a != b) {
			if (lvl[a] < lvl[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;
}

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++)
......
   86 |  REP (i, 1, adj[u].size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
pipes.cpp:86:2: note: in expansion of macro 'REP'
   86 |  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 3 ms 3404 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 11784 KB Output is correct
2 Correct 126 ms 11816 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 11972 KB Output is correct
2 Runtime error 262 ms 20224 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 426 ms 20508 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 614 ms 22012 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 995 ms 38824 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1331 ms 39404 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 785 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 708 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -