Submission #1132952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132952		Kubeti	Pipes (CEOI15_pipes)	C++20	10 / 100	2148 ms	98012 KiB

pipes

#include <bits/stdc++.h>
#define maxn 1<<17
#define pb push_back
using namespace std;
vector<int> V[maxn],RS[maxn];
int N,M,T[maxn],P[maxn],rs,St[maxn],st;
bool f[maxn];
void dfs(int x){
    f[x] = 1;
    St[++st] = x;
    for(auto y:V[x]) if(P[y]) P[x] = min(P[x],T[y]);
    else{
        int p=st;
        P[y] = T[y] = T[x] + 1;
        dfs(y);
        P[x] = min(P[x],P[y]);
        if(P[y] >= T[x]){
            RS[++rs].pb(x);
            while(p<st) RS[rs].pb(St[st--]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> N >> M;
    for(int x,y;M--;){
        cin >> x >> y;
        V[x].pb(y); V[y].pb(x);
    }
    for(int i = 1; i <= N; i++) {
      if(f[i]) {
        continue;
      }
      st = 0;
      T[i] = P[i] = 1;
      dfs(i);
    }
    while(rs >= 0){
        if(RS[rs].size() == 2) {
          for(auto it : RS[rs]) {
            cout << it << " ";
          }
          cout << '\n';
        }
        rs--;
    }
}

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