Submission #46452

#TimeUsernameProblemLanguageResultExecution timeMemory
46452alex99Pipes (CEOI15_pipes)C++14
100 / 100
4106 ms7516 KiB
#include <iostream> #include <vector> #include <cstdlib> #include <ctime> using namespace std; int N, M; int TT[100005], R[100005]; long long Sum[100005]; vector <int> G[100005]; bool Use[100005]; void Unite(int x, int y) { if(x == y) return; if(R[x] < R[y]) { TT[x] = y; } else TT[y] = x; if(R[x] == R[y]) R[x]++; } int Father(int x) { int init = x; while(x != TT[x]) x = TT[x]; while(init != x) { int next = TT[init]; TT[init] = x; init = next; } return x; } void DFS(int node, int father) { Use[node] = 1; for(int i = 0; i < G[node].size(); i++) { int neighb = G[node][i]; if(neighb == father) continue; DFS(neighb, node); Sum[node] += Sum[neighb]; } if(Sum[node] == 0 && father != 0) { cout << node << " " << father << "\n"; } } void Solve() { cin >> N >> M; for(int i = 1; i <= N; i++) TT[i] = i; for(int i = 1; i <= M; i++) { int x, y; cin >> x >> y; if(Father(x) == Father(y)) { int r = rand(); Sum[x] += r; Sum[y] -= r; } else { G[x].push_back(y); G[y].push_back(x); Unite(Father(x), Father(y)); } } for(int i = 1; i <= N; i++) if(Use[i] == 0) DFS(i, 0); } int main() { srand(time(NULL)); Solve(); return 0; }

Compilation message (stderr)

pipes.cpp: In function 'void DFS(int, int)':
pipes.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < G[node].size(); i++)
                    ~~^~~~~~~~~~~~~~~~
#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...