제출 #43843

#제출 시각아이디문제언어결과실행 시간메모리
43843BruteforcemanPipes (BOI13_pipes)C++11
100 / 100
347 ms20744 KiB
#include "bits/stdc++.h" using namespace std; bool vis[100010]; int l[500010], r[500010]; vector <int> g[100010]; long long a[100010]; bool del[500010]; int deg[100010]; long long ans[500010]; vector <int> can; bool bad; void check(int x) { vis[x] = true; can.push_back(x); int deg = 0; for(auto i : g[x]) { if(del[i]) continue; int y = l[i] ^ r[i] ^ x; ++deg; if(vis[y] == false) check(y); } if(deg != 2 && deg != 0) { bad = true; } } int edge(int x, int y) { for(auto i : g[x]) { int p = l[i] ^ r[i] ^ x; if(p == y) return i; } return -1; } void solve(vector <int> v) { int size = v.size(); vector <long long> Odd (size), Even (size); long long odd = 0; long long even = 0; long long sum = 0; for(int i = 0; i < size; i++) { if(i & 1) { odd += a[v[i]]; } else { even += a[v[i]]; } Even[i] = even; Odd[i] = odd; sum += a[v[i]]; } if(sum % 2 != 0) { printf("0\n"); exit(0); } sum /= 2; for(int i = 0; i < size; i++) { int p = v[i]; int q = v[(i + 1) % size]; int id = edge(p, q); if(i & 1) { ans[id] = Even[i]; ans[id] += odd - Odd[i]; } else { ans[id] = Odd[i]; ans[id] += even - Even[i]; } ans[id] = sum - ans[id]; } } int main(int argc, char const *argv[]) { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } queue <int> Q; for(int i = 1; i <= m; i++) { int p, q; scanf("%d %d", &p, &q); g[p].push_back(i); g[q].push_back(i); l[i] = p; r[i] = q; } for(int i = 1; i <= n; i++) { deg[i] = g[i].size(); if(g[i].size() == 1) { Q.push(i); } } while(!Q.empty()) { int p = Q.front(); Q.pop(); if(deg[p] != 1) { if(a[p] != 0) { printf("0\n"); exit(0); } continue; } for(auto i : g[p]) { if(del[i] == true) continue; int j = l[i] ^ r[i] ^ p; deg[j]--; if(deg[j] == 1) { Q.push(j); } ans[i] = a[p]; a[j] -= a[p]; del[i] = true; } } for(int i = 1; i <= n; i++) { if(vis[i] == false) { bad = false; can.clear(); check(i); if(can.size() % 2 == 0) { bad = true; } if(bad) { printf("0\n"); exit(0); } if(can.size() > 1) { solve(can); } } } for(int i = 1; i <= m; i++) { printf("%lld\n", ans[i] << 1); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'int main(int, const char**)':
pipes.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
pipes.cpp:75:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^
pipes.cpp:80:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...