Submission #44877

#TimeUsernameProblemLanguageResultExecution timeMemory
44877bogdan10bosPipes (CEOI15_pipes)C++14
30 / 100
2395 ms65536 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef pair<int, int> pii; int N, M; int K, vis[100005], lst[100005]; vector<int> nodes, edg[100005]; vector<pii> critical; int q[100005]; int f[2][100005]; void init(int id, int N) { for(int i = 1; i <= N; i++) f[id][i] = i; } int F(int id, int x) { if(f[id][x] == x) return x; return f[id][x] = F(id, f[id][x]); } void unite(int id, int x, int y) { if(F(id, x) == F(id, y)) return; f[id][F(id, y)] = F(id, x); } /*class UnionFind { public: int N; int f[100005]; void init(int _N) { N = _N; for(int i = 1; i <= N; i++) f[i] = i; } int F(int x) { if(f[x] == x) return x; return f[x] = F(f[x]); } void unite(int x, int y) { if(F(x) == F(y)) return; f[F(y)] = F(x); } }; UnionFind f[2];*/ void gen() { freopen("1.in", "w", stdout); int N = 10000; int M = 1e6; printf("%d %d\n", N, M); auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 gene(seed); uniform_int_distribution<int> uid(1, N); for(int i = 1; i <= M; i++) { int x = uid(gene); int y = uid(gene); printf("%d %d\n", x, y); } exit(0); } int main() { //gen(); #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &M); init(0, N), init(1, N); int mx = 0; for(int i = 1; i <= M; i++) { /*int cnt = 0; for(int i = 1; i <= N; i++) cnt += edg[i].size(); mx = max(mx, cnt); assert(critical.size() <= N);*/ int x, y; scanf("%d%d", &x, &y); if(F(0, x) != F(0, y)) { critical.push_back({x, y}); unite(0, x, y); int fx = F(1, x); int fy = F(1, y); edg[fx].push_back(fy); edg[fy].push_back(fx); continue; } if(F(1, x) == F(1, y)) continue; x = F(1, x); y = F(1, y); nodes.clear(); nodes.push_back(x); nodes.push_back(y); K += 2; vis[x] = K; vis[y] = K + 1; int st = 1, dr = 2; q[1] = x; q[2] = y; while(st <= dr) { int nod = q[st]; int id = vis[nod]; st++; for(auto nxt: edg[nod]) { nxt = F(1, nxt); if(vis[nxt] == id) continue; if(vis[nxt] == (id ^ 1)) { int nd1 = nod; int nd2 = nxt; if(vis[nod] != K) swap(nd1, nd2); while(nd1 != x) { nodes.push_back(nd1); nd1 = lst[nd1]; } while(nd2 != y) { nodes.push_back(nd2); nd2 = lst[nd2]; } st = dr + 1; break; } vis[nxt] = vis[nod]; lst[nxt] = nod; q[++dr] = nxt; } } for(int i = 1; i < nodes.size(); i++) { unite(1, nodes[0], nodes[i]); for(auto x: edg[ nodes[i] ]) if(F(1, x) != F(1, nodes[0])) edg[ nodes[0] ].push_back(x); edg[ nodes[i] ].clear(); } for(int i = 0; i < edg[ nodes[0] ].size(); i++) { if(F( 1, nodes[0] ) == F( 1, edg[ nodes[0] ][i])) { edg[ nodes[0] ].erase(edg[ nodes[0] ].begin() + i); i--; } } for(int i = 0; i < critical.size(); i++) if( F(1, critical[i].first) == F(1, critical[i].second) ) { critical.erase(critical.begin() + i); i--; } } for(auto e: critical) if(F(1, e.first) != F(1, e.second)) printf("%d %d\n", e.first, e.second); //cerr << mx << '\n'; return 0; }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:165:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < nodes.size(); i++)
                        ~~^~~~~~~~~~~~~~
pipes.cpp:173:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < edg[ nodes[0] ].size(); i++)
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:182:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < critical.size(); i++)
                        ~~^~~~~~~~~~~~~~~~~
pipes.cpp:89:9: warning: unused variable 'mx' [-Wunused-variable]
     int mx = 0;
         ^~
pipes.cpp: In function 'void gen()':
pipes.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#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...