oj.uz

Submission #362683

# Submission time Handle Problem Language Result Execution time Memory
362683 2021-02-04T05:53:16 Z ijxjdjd Pipes (CEOI15_pipes) C++14
40 / 100
 5000 ms 47316 KB 
#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 = 18;
int up[MAXN][MAXK];
int sm[MAXN];
int rt[MAXN];
int sz[MAXN];
bool bad[MAXN];
int depth[MAXN];
vector<int> ch[MAXN];
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;
    }
}
int reset(int n, int p, int d, int o) {
    up[n][0] = p;
    sm[n] = 0;
    sz[n] = 1;
    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) {
            sz[n] += reset(e, n, d+1, o);
        }
    }
    return sz[n];
}
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) {
    int low = 0;
    int high = min(depth[u], depth[v]);
    while (low < high) {
        int mid = (low + high+1)/2;
        if (getUp(u, depth[u] - mid) == getUp(v, depth[v] - mid)) {
            low = mid;
        }
        else {
            high = mid-1;
        }
    }
    return getUp(u, depth[u] - low);
}
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);
        }
        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);
                }
                sz[rt[v]] += reset(u, v, depth[v]+1, 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]] += 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 2 ms 2668 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3308 KB Output is correct
2 Correct 10 ms 3308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 8684 KB Output is correct
2 Correct 339 ms 8428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 13524 KB Output is correct
2 Correct 847 ms 15272 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5021 ms 31596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5099 ms 36884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -