Submission #1203871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203871		12345678	Pipes (CEOI15_pipes)	C++20	80 / 100	570 ms	17036 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, m, u, v, sz[nx], dsu1[nx], dsu2[nx], low[nx], disc[nx], t, rt;
vector<pair<int ,int>> d[nx];

int find1(int x)
{
    if (dsu1[x]==x) return x;
    return dsu1[x]=find1(dsu1[x]);
}

int find2(int x)
{
    if (dsu2[x]==x) return x;
    return dsu2[x]=find2(dsu2[x]);
}

void dfs(int u, int p, int pidx)
{
    low[u]=disc[u]=++t;
    for (auto [v, idx]:d[u])
    {
        if (idx==pidx) continue;
        if (!disc[v]) dfs(v, u, idx), low[u]=min(low[u], low[v]);
        else low[u]=min(low[u], disc[v]);
    }
    if (low[u]==disc[u]&&u!=rt) cout<<u<<' '<<p<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n ;i++) dsu1[i]=dsu2[i]=i;
    for (int i=1; i<=m; i++)
    {
        cin>>u>>v;
        if (find1(u)!=find1(v))
        {
            dsu1[find1(u)]=find1(v);
            d[u].push_back({v, i});
            d[v].push_back({u, i});
        }
        else if (find2(u)!=find2(v))
        {
            dsu2[find2(u)]=find2(v);
            d[u].push_back({v, i});
            d[v].push_back({u, i});
        }
    }
    for (int i=1; i<=n; i++) if (!disc[i]) rt=i, dfs(i, i, -1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10