oj.uz

Submission #362695

# Submission time Handle Problem Language Result Execution time Memory
362695 2021-02-04T06:31:25 Z ijxjdjd Pipes (CEOI15_pipes) C++14
100 / 100
 3595 ms 14388 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 100000;
const int MAXK = 17;
int up[MAXN][MAXK];
int sm[MAXN];
int rt[MAXN];
int sz[MAXN];
bool bad[MAXN];
int depth[MAXN];
vector<int> ch[MAXN];
int cnt = 0;
void makeBad(int n, int p) {
    for (int e : ch[n]) {
        if (e != p) {
            makeBad(e, n);
            sm[n] += sm[e];
        }
    }
    if (sm[n] > 0) {
        bad[n] = true;
    }
}
void reset(int n, int p, int d, int o) {
    up[n][0] = p;
    sm[n] = 0;
    rt[n] = o;
    depth[n] = d;
    for (int i = 1; i < MAXK; i++) {
        up[n][i] = up[up[n][i-1]][i-1];
    }
    for (int e : ch[n]) {
        if (e != p) {
            reset(e, n, d+1, o);
        }
    }
}
int getUp(int u, int k) {
    for (int i = 0; i < MAXK; i++) {
        if (k&(1<<i)) {
            u = up[u][i];
        }
    }
    return u;
}
int lca(int u, int v) {
    if (depth[u] > depth[v]) {
        swap(u, v);
    }
    v = getUp(v, depth[v] - depth[u]);
    if (u == v) {
        return u;
    }
    for (int k = MAXK-1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	FR(i, N) {
        up[i][0] = -1;
	}
	FR(i, M) {
	    int u, v;
        cin >> u >> v;
        u--, v--;
        if (up[u][0] == -1 && up[v][0] == -1) {
            ch[u].push_back(v);
            ch[v].push_back(u);
            reset(u, u, 0, u);
            sz[u] = 2;
        }
        else {
            if (up[u][0] == -1 || up[v][0] == -1) {
                ch[u].push_back(v);
                ch[v].push_back(u);
                if (up[v][0] == -1) {
                    swap(u, v);
                }
                reset(u, v, depth[v]+1, rt[v]);
                sz[rt[v]]++;
            }
            else {
                if (rt[u] == rt[v]) {
                    int x = lca(u, v);
                    sm[x] -= 2;
                    sm[u]++;
                    sm[v]++;
                }
                else {
                    if (sz[rt[u]] > sz[rt[v]]) {
                        swap(u, v);
                    }
                    int j = u;
                    bool last = false;
                    makeBad(rt[u], rt[u]);
                    while (true) {
                        swap(bad[j], last);
                        if (j == up[j][0]) {
                            break;
                        }
                        j = up[j][0];
                    }
                    ch[u].push_back(v);
                    ch[v].push_back(u);
                    sz[rt[v]] += sz[rt[u]];
                    reset(u, v, depth[v]+1, rt[v]);
                }
            }
        }
	}
	FR(i, N) {
	    if (up[i][0] == i) {
            makeBad(i, i);
	    }
	}
	FR(i, N) {
        if (up[i][0] != i && up[i][0] != -1 && !bad[i]) {
            cout << i+1 <<  " " << up[i][0] + 1 << '\n';
        }
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3180 KB Output is correct
2 Correct 8 ms 3180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3052 KB Output is correct
2 Correct 159 ms 3180 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 3820 KB Output is correct
2 Correct 354 ms 3948 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 5356 KB Output is correct
2 Correct 446 ms 6212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 10760 KB Output is correct
2 Correct 881 ms 10924 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1680 ms 12140 KB Output is correct
2 Correct 1296 ms 12040 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2437 ms 14076 KB Output is correct
2 Correct 2356 ms 14388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2928 ms 14088 KB Output is correct
2 Correct 3052 ms 14188 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3595 ms 13552 KB Output is correct
2 Correct 2805 ms 14180 KB Output is correct