Submission #518897

#TimeUsernameProblemLanguageResultExecution timeMemory
518897bluePipes (BOI13_pipes)C++17
65 / 100
815 ms23920 KiB
#include <iostream> #include <vector> #include <queue> using namespace std; using ll = long long; using pl = pair<ll, ll>; using vpl = vector<pl>; using pii = pair<int, int>; using vi = vector<int>; using vl = vector<ll>; const int mx = 100'000; const int emx = 500'000; vl c(1+mx); vector<pii> edge[1+mx]; vi deg(1+mx, 0); vi visit(1+emx, 0); vector<ll> ans(1+emx); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; for(int i = 1; i <= N; i++) cin >> c[i]; for(int j = 1; j <= M; j++) { int u, v; cin >> u >> v; edge[u].push_back({v, j}); edge[v].push_back({u, j}); deg[u]++; deg[v]++; } if(M > N) { cout << "0\n"; return 0; } queue<int> tbv; for(int i = 1; i <= N; i++) { if(deg[i] == 1) { tbv.push(i); } } int endv = -1; while(!tbv.empty()) { int u = tbv.front(); tbv.pop(); // cerr << "u = " << u << '\n'; int elim = 0; for(auto ed: edge[u]) { int v = ed.first; if(visit[ed.second]) continue; visit[ed.second] = 1; deg[v]--; elim = 1; if(deg[v] <= 1) { tbv.push(v); } ans[ed.second] = 2*c[u]; cerr << ed.first << ' ' << ed.second << " : " << 2*c[u] << '\n'; c[v] -= c[u]; c[u] -= c[u]; } if(!elim) { if(M == N-1) { if(c[u] != 0) { cout << "0\n"; return 0; } } } } for(int e = 1; e <= M; e++) { cout << ans[e] << '\n'; } }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:59:6: warning: unused variable 'endv' [-Wunused-variable]
   59 |  int endv = -1;
      |      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...