oj.uz

Submission #81944

# Submission time Handle Problem Language Result Execution time Memory
81944 2018-10-28T07:59:24 Z Saboon Pipes (CEOI15_pipes) C++14
50 / 100
 1335 ms 7296 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#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 = 3e4 + 10;
const ll inf = 1e18 + 1000;

int h[maxn], par[maxn][22], dp[maxn];
bool cut[maxn];

int lca (int v, int u) {
    if (h[v] < h[u])
        swap (v, u);
    for (int i = 20; i >= 0; i--)
        if (h[v] - (1 << i) >= h[u])
            v = par[v][i];
    if (v == u)
        return v;
    for (int i = 20; 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];

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

void dfs1 (int v, int p) {
    par[v][0] = p;
    for (int i = 1; i <= 20; i++) {
        if (par[v][i - 1] != -1)
            par[v][i] = par[par[v][i - 1]][i - 1];
        else
            par[v][i] = -1;
    }
    for (auto u : g[v]) {
        if (u != p) {
            dfs1 (u, v);
        if (h[v] > h[u])
            cut[u] = cut[v];
        }
    }
}

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];
int get_par (int v) {
    if (dpar[v] < 0)
        return v;
    return dpar[v] = get_par (dpar[v]);
}

int n;
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);
}

bool mark[maxn];

int main() {
    memset (par, -1, sizeof par);
    memset (dpar, -1, sizeof dpar);
    int m;
    cin >> n >> m;
    while (m --) {
        int v, u;
        cin >> 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++) {
        int v = get_par (i);
        if (!mark[v]) {
            mark[v] = 1;
            dfs (v);
        }
    }
    for (int i = 1; i <= n; i++)
        if (cut[i])
            cout << i << " " << par[i][0] << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3968 KB Output is correct
2 Correct 13 ms 3840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 3920 KB Output is correct
2 Correct 364 ms 3920 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 4164 KB Output is correct
2 Correct 860 ms 4096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 4728 KB Output is correct
2 Correct 1075 ms 4984 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -