Submission #585221

#	Time	Username	Problem	Language	Result	Execution time	Memory
585221		MohammadAghil	Pipes (BOI13_pipes)	C++17	0 / 100	27 ms	24436 KiB

pipes

#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 5e5+5, inf = ll(1e9)+5;

vector<pp> adj[maxn];
bool vis[maxn], mrk[maxn];
vector<pp> edge;

void dfs(int r){
     vector<pp> stk{{r, -1}};
     while(sz(stk)){
          auto[r, lst] = stk.back();
          if(lst + 1) edge.pb({r, lst}), stk.back().ss = -1;
          mrk[r] = true;
          if(sz(adj[r])){
               auto[id, u] = adj[r].back(); adj[r].pop_back();
               if(vis[id]) continue;
               vis[id] = true;
               stk.back().ss = u;
               stk.pb({u, -1});
          }else stk.pop_back();
     }
}

// void dfs(int r){
//      mrk[r] = true;
//      while(sz(adj[r])){
//           auto[id, u] = adj[r].back(); adj[r].pop_back();
//           if(vis[id]) continue;
//           vis[id] = true;
//           dfs(u);
//           edge.pb({r, u});
//      }
// }

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          freopen("in.in", "r", stdin);
          freopen("out.out", "w", stdout);
     #endif
     int n, m; cin >> n >> m;
     rep(i,0,m){
          int u, v; cin >> u >> v; u--, v--;
          adj[u].pb({i, v}), adj[v].pb({i, u});
     }
     rep(i,0,n) if(!mrk[i]) dfs(i);
     reverse(all(edge));
     // for(auto[u, v]: edge) cout << ++u << ' ' << ++v << '\n';
     vector<int> stk{edge[0].ff};
     fill(mrk, mrk + n, false); mrk[edge[0].ff] = true;
     rep(i,0,m){
          auto[u, v] = edge[i];
          if(mrk[v]){
               while(true){
                    int r = stk.back(); stk.pop_back();
                    mrk[r] = false;
                    cout << r+1 << ' ';
                    if(r == v) break; 
               } cout << '\n';
          }
          mrk[v] = true;
          stk.pb(v);
     }
     return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:53:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |           freopen("in.in", "r", stdin);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:54:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |           freopen("out.out", "w", stdout);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70