oj.uz

Submission #585221

# Submission time Handle Problem Language Result Execution time Memory
585221 2022-06-28T12:45:56 Z MohammadAghil Pipes (BOI13_pipes) C++17
0 / 100
 27 ms 24436 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24432 KB Execution killed with signal 11
2 Runtime error 18 ms 24300 KB Execution killed with signal 11
3 Runtime error 21 ms 24356 KB Execution killed with signal 11
4 Runtime error 19 ms 24388 KB Execution killed with signal 11
5 Runtime error 19 ms 24296 KB Execution killed with signal 11
6 Runtime error 21 ms 24404 KB Execution killed with signal 11
7 Runtime error 17 ms 24320 KB Execution killed with signal 11
8 Runtime error 17 ms 24380 KB Execution killed with signal 11
9 Runtime error 17 ms 24312 KB Execution killed with signal 11
10 Runtime error 22 ms 24368 KB Execution killed with signal 11
11 Runtime error 19 ms 24396 KB Execution killed with signal 11
12 Runtime error 22 ms 24348 KB Execution killed with signal 11
13 Runtime error 16 ms 24404 KB Execution killed with signal 11
14 Runtime error 19 ms 24424 KB Execution killed with signal 11
15 Runtime error 23 ms 24300 KB Execution killed with signal 11
16 Runtime error 17 ms 24300 KB Execution killed with signal 11
17 Runtime error 21 ms 24300 KB Execution killed with signal 11
18 Runtime error 17 ms 24404 KB Execution killed with signal 11
19 Runtime error 21 ms 24404 KB Execution killed with signal 11
20 Runtime error 16 ms 24404 KB Execution killed with signal 11
21 Runtime error 18 ms 24304 KB Execution killed with signal 11
22 Runtime error 17 ms 24404 KB Execution killed with signal 11
23 Runtime error 17 ms 24388 KB Execution killed with signal 11
24 Runtime error 22 ms 24396 KB Execution killed with signal 11
25 Runtime error 18 ms 24360 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 24312 KB Execution killed with signal 11
2 Runtime error 21 ms 24396 KB Execution killed with signal 11
3 Runtime error 22 ms 24404 KB Execution killed with signal 11
4 Runtime error 22 ms 24316 KB Execution killed with signal 11
5 Runtime error 25 ms 24316 KB Execution killed with signal 11
6 Runtime error 17 ms 24360 KB Execution killed with signal 11
7 Runtime error 18 ms 24320 KB Execution killed with signal 11
8 Runtime error 18 ms 24308 KB Execution killed with signal 11
9 Runtime error 18 ms 24424 KB Execution killed with signal 11
10 Runtime error 22 ms 24344 KB Execution killed with signal 11
11 Runtime error 19 ms 24308 KB Execution killed with signal 11
12 Runtime error 17 ms 24400 KB Execution killed with signal 11
13 Runtime error 18 ms 24408 KB Execution killed with signal 11
14 Runtime error 20 ms 24300 KB Execution killed with signal 11
15 Runtime error 21 ms 24332 KB Execution killed with signal 11
16 Runtime error 18 ms 24388 KB Execution killed with signal 11
17 Runtime error 20 ms 24360 KB Execution killed with signal 11
18 Runtime error 18 ms 24292 KB Execution killed with signal 11
19 Runtime error 18 ms 24404 KB Execution killed with signal 11
20 Runtime error 17 ms 24436 KB Execution killed with signal 11
21 Runtime error 24 ms 24304 KB Execution killed with signal 11
22 Runtime error 22 ms 24404 KB Execution killed with signal 11
23 Runtime error 21 ms 24396 KB Execution killed with signal 11
24 Runtime error 19 ms 24396 KB Execution killed with signal 11
25 Runtime error 18 ms 24380 KB Execution killed with signal 11
26 Runtime error 19 ms 24292 KB Execution killed with signal 11
27 Runtime error 17 ms 24348 KB Execution killed with signal 11
28 Runtime error 18 ms 24360 KB Execution killed with signal 11
29 Runtime error 21 ms 24376 KB Execution killed with signal 11
30 Runtime error 20 ms 24372 KB Execution killed with signal 11
31 Runtime error 18 ms 24432 KB Execution killed with signal 11
32 Runtime error 23 ms 24328 KB Execution killed with signal 11
33 Runtime error 19 ms 24404 KB Execution killed with signal 11
34 Runtime error 17 ms 24384 KB Execution killed with signal 11
35 Runtime error 23 ms 24372 KB Execution killed with signal 11
36 Runtime error 17 ms 24360 KB Execution killed with signal 11
37 Runtime error 17 ms 24312 KB Execution killed with signal 11
38 Runtime error 18 ms 24404 KB Execution killed with signal 11
39 Runtime error 18 ms 24372 KB Execution killed with signal 11
40 Runtime error 23 ms 24408 KB Execution killed with signal 11
41 Runtime error 19 ms 24420 KB Execution killed with signal 11
42 Runtime error 20 ms 24376 KB Execution killed with signal 11
43 Runtime error 17 ms 24404 KB Execution killed with signal 11
44 Runtime error 20 ms 24404 KB Execution killed with signal 11
45 Runtime error 24 ms 24308 KB Execution killed with signal 11
46 Runtime error 18 ms 24380 KB Execution killed with signal 11
47 Runtime error 18 ms 24308 KB Execution killed with signal 11
48 Runtime error 22 ms 24356 KB Execution killed with signal 11
49 Runtime error 17 ms 24300 KB Execution killed with signal 11
50 Runtime error 21 ms 24344 KB Execution killed with signal 11
51 Runtime error 20 ms 24300 KB Execution killed with signal 11
52 Runtime error 16 ms 24300 KB Execution killed with signal 11
53 Runtime error 27 ms 24360 KB Execution killed with signal 11
54 Runtime error 20 ms 24400 KB Execution killed with signal 11