Submission #728073

#	Time	Username	Problem	Language	Result	Execution time	Memory
728073		n0sk1ll	Pipes (CEOI15_pipes)	C++17	100 / 100	968 ms	13348 KiB

pipes

#include <vector>
#include <iostream>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
 
using namespace std;
 
int up[2][100005];
 
int Up(bool c, int x)
{
    if (up[c][x]<0) return x;
    return up[c][x]=Up(c,up[c][x]);
}
 
bool dsu(bool c, int a, int b)
{
    a=Up(c,a),b=Up(c,b);
    if (a==b) return false;
    if (up[c][a]<up[c][b]) swap(a,b);
    up[c][b]+=up[c][a],up[c][a]=b;
    return true;
}
 
int par[100010];
int idx[100010];
int lowl[100010];
int nt;
vector<int> edge[100010];
 
void dfs(int x){
	idx[x] = lowl[x] = ++nt;
	bool cl = false;
	for(int y:edge[x]){
		if(par[x] == y && !cl){
			cl=true; continue;
		}
		if(!idx[y]){
			par[y]=x;
			dfs(y);
			lowl[x] = min(lowl[x], lowl[y]);
		} else lowl[x] = min(lowl[x], idx[y]);
	}
	if(par[x] && idx[x]==lowl[x]) cout<<x<<" "<<par[x]<<"\n";
}
 
int main()
{
    FAST;
 
    int n,m; cin>>n>>m;
    for (int c=0;c<2;c++) for (int i=1;i<=n;i++) up[c][i]=-1;
 
    while (m--)
    {
        int u,v; cin>>u>>v;
        if (dsu(0,u,v) || dsu(1,u,v)) edge[u].push_back(v),edge[v].push_back(u);
    }
 
    for (int i=1;i<=n;i++) if (up[0][i]<0) dfs(i);
}

• 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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10