Submission #46455

#TimeUsernameProblemLanguageResultExecution timeMemory
46455alex99Pipes (CEOI15_pipes)C++14
100 / 100
1468 ms7896 KiB
#include <iostream> #include <vector> #include <cstdlib> #include <cstdio> #include <ctime> using namespace std; int N, M; int TT[100005], R[100005]; long long Sum[100005]; int F[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) { Use[node] = 1; for(int i = 0; i < G[node].size(); i++) { int neighb = G[node][i]; if(neighb == F[node]) continue; F[neighb] = node; DFS(neighb); Sum[node] += Sum[neighb]; } if(Sum[node] == 0 && F[node] != 0) { printf("%d %d\n", node, F[node]); } } void Solve() { scanf("%d%d", &N, &M); for(int i = 1; i <= N; i++) TT[i] = i; for(int i = 1; i <= M; i++) { int x, y; scanf("%d%d", &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); } int main() { srand(time(NULL)); Solve(); return 0; }

Compilation message (stderr)

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