oj.uz

Submission #444594

# Submission time Handle Problem Language Result Execution time Memory
444594 2021-07-14T10:12:11 Z prvocislo Pipes (CEOI15_pipes) C++17
100 / 100
 1345 ms 13000 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5;
struct dsu
{
    int p[maxn];
    int root(int r) { return r == p[r] ? r : p[r] = root(p[r]); }
    bool merge(int a, int b)
    {
        a = root(a), b = root(b);
        if (a == b) return false;
        p[a] = b;
        return true;
    }
    dsu() { for (int i = 0; i < maxn; i++) p[i] = i; }
} d[2];
int tin[maxn], low[maxn], n, m, timer = 0;
vector<int> g[maxn];
void bridge(int a, int b) { cout << a+1 << " " << b+1 << "\n"; }
void dfs(int u, int p)
{
    low[u] = tin[u] = ++timer;
    bool seen = false;
    for (int v : g[u])
    {
        if (v == p && !seen) seen = true;
        else if (tin[v]) low[u] = min(low[u], tin[v]);
        else
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
    }
    if (p != -1 && tin[u] == low[u])
         bridge(u, p);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> m;
    int cnt = 0;
    for (int i = 0, a, b; i < m; i++)
    {
        cin >> a >> b; a--, b--;
        if (d[0].merge(a, b))
        {cnt++;
            //cout << "edge " << a << " " << b << endl;
            g[a].push_back(b), g[b].push_back(a);
        }
        else if (d[1].merge(a, b))
        {cnt++;
            //cout << "edge " << a << " " << b << endl;
            g[a].push_back(b), g[b].push_back(a);
        }
    }
    //cout << cnt << "\n";
    assert(cnt <= 2 * n - 2);
    for (int i = 0; i < n; i++) if (!tin[i]) dfs(i, -1);
    return 0;
}

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 6 ms 3696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 3720 KB Output is correct
2 Correct 112 ms 3572 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 4340 KB Output is correct
2 Correct 253 ms 3944 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 5660 KB Output is correct
2 Correct 290 ms 5388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 10112 KB Output is correct
2 Correct 391 ms 7204 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 11220 KB Output is correct
2 Correct 651 ms 8764 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 13000 KB Output is correct
2 Correct 862 ms 8964 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 12944 KB Output is correct
2 Correct 1069 ms 8988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 12484 KB Output is correct
2 Correct 1269 ms 10024 KB Output is correct