Submission #1034727

#TimeUsernameProblemLanguageResultExecution timeMemory
1034727vjudge1Pipes (CEOI15_pipes)C++17
40 / 100
686 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'010; struct dsu { int e[N]; int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); } bool join(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (e[a] > e[b]) swap(a, b); e[a] += e[b]; e[b] = a; return true; } } d1, d2; vector<int> g[N]; int timer=0; void dfs(int &at, int &par) { bool ck=0; d1.e[at]=d2.e[at]=++timer; for(int &to:g[at]) { if(to == par and ck==0) { ck=1; continue; } if(d2.e[to]) { d1.e[at]=min(d1.e[at], d2.e[to]); } else { dfs(to, at); d1.e[at]=min(d1.e[at], d1.e[to]); } } if(d1.e[at] == d2.e[at] and at!=par) { cout << at << " " << par << "\n"; } } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int n, m; cin >> n >> m; int u, v; for(int i = 1;i<N;i++)d1.e[i]=d2.e[i]=-1; for(int i = 0;i<m;i++) { cin >> u >> v; if(d1.join(u, v) || d2.join(u, v)) { g[u].push_back(v); g[v].push_back(u); } } for(int i = 1;i<=N;i++)d1.e[i]=d2.e[i]=0; for(int i= 1;i<=n;i++) { if(!d1.e[i]) { dfs(i, i); } } }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:51:40: warning: iteration 100009 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |  for(int i = 1;i<=N;i++)d1.e[i]=d2.e[i]=0;
      |                                 ~~~~~~~^~
pipes.cpp:51:17: note: within this loop
   51 |  for(int i = 1;i<=N;i++)d1.e[i]=d2.e[i]=0;
      |                ~^~~
pipes.cpp:51:40: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [400040, 400043] is out of the bounds [0, 400040] of object 'd2' with type 'dsu' [-Warray-bounds]
   51 |  for(int i = 1;i<=N;i++)d1.e[i]=d2.e[i]=0;
      |                                 ~~~~~~~^~
pipes.cpp:15:7: note: 'd2' declared here
   15 | } d1, d2;
      |       ^~
pipes.cpp:51:32: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [400040, 400043] is out of the bounds [0, 400040] of object 'd1' with type 'dsu' [-Warray-bounds]
   51 |  for(int i = 1;i<=N;i++)d1.e[i]=d2.e[i]=0;
      |                         ~~~~~~~^~~~~~~~~~
pipes.cpp:15:3: note: 'd1' declared here
   15 | } d1, d2;
      |   ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...