제출 #125144

#제출 시각아이디문제언어결과실행 시간메모리
125144thiago4532Pipes (BOI13_pipes)C++17
100 / 100
455 ms24832 KiB
#include <bits/stdc++.h> #define int int64_t using namespace std; const int maxn = 1e5 + 10; bool mark[maxn]; int ans[5*maxn], s[maxn], grau[maxn]; map<pair<int, int>, int> mapa; int n; vector<int> grafo[maxn]; bool marca[maxn]; int32_t main() { int m; cin >> n >> m; if(m > n) { cout << "0\n"; return 0; } int total = 0; for(int i=1;i<=n;i++) cin >> s[i], s[i] *= 2, total += s[i]; for(int i=1;i<=m;i++) { int a, b; cin >> a >> b; grafo[a].push_back(b); grafo[b].push_back(a); mapa[{a, b}] = i; mapa[{b, a}] = i; grau[a]++; grau[b]++; } queue<int> fila; for(int i=1;i<=n;i++) { if(grau[i] == 1) fila.push(i); } while(!fila.empty()) { int u = fila.front(); fila.pop(); if(mark[u]) continue; mark[u] = true; // cout << u << ": " << s[u] << "\n"; for(auto v : grafo[u]) { if(mark[v]) continue; grau[v]--; ans[mapa[{u, v}]] = s[u], s[v] -= s[u]; if(grau[v] == 1) fila.push(v); } } vector<int> ciclo; for(int i=1;i<=n;i++) if(!mark[i]) ciclo.push_back(i); if(ciclo.size() == 0) { for(int i=1;i<=m;i++) cout << ans[i] << "\n"; return 0; } // cout << "SHITE\n" if(ciclo.size() % 2 == 0){ cout << "0\n"; return 0; } vector<int> ordem; int k = 0; ordem.push_back(ciclo[0]); while(k < ordem.size()) { int u = ordem[k++]; if(marca[u]) continue; marca[u] = true; for(auto v : grafo[u]) { if(mark[v] || marca[v]) continue; ordem.push_back(v); break; } } int sums = 0; int val = 1; for(auto u : ordem) { sums += (s[u] * val); val *= -1; } sums >>= 1; ans[mapa[{ordem.back(), ordem.front()}]] = sums; int l = sums; for(int i = 0; i < (int)ordem.size() - 1;i++) { ans[mapa[{ordem[i], ordem[i+1]}]] = s[ordem[i]] - l; l = s[ordem[i]] - l; } for(int i=1;i<=m;i++) cout << ans[i] << "\n"; return 0; }

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

pipes.cpp: In function 'int32_t main()':
pipes.cpp:80:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(k < ordem.size()) {
        ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...