Submission #698542

#TimeUsernameProblemLanguageResultExecution timeMemory
698542_martynasPipes (BOI13_pipes)C++11
72.78 / 100
178 ms23996 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define PB push_back using ll = long long; using vi = vector<int>; using pii = pair<int, int>; const int MXN = 1e5+5; int n, m; ll C[MXN]; vector<pii> adj[MXN]; int degree[MXN]; ll E[5*MXN]; bool visited[MXN]; void dfs(int u, vi &comp) { visited[u] = true; comp.PB(u); for(auto p : adj[u]) { int v = p.F; if(visited[v]) continue; dfs(v, comp); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> C[i]; for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].PB({b, i}); adj[b].PB({a, i}); } queue<int> Q; for(int i = 1; i <= n; i++) { degree[i] = adj[i].size(); if(degree[i] == 1) Q.push(i); } while(!Q.empty()) { int u = Q.front(); Q.pop(); degree[u] = 0; for(auto p : adj[u]) { if(degree[p.F]) { // there should only be one v that satisfies this condition E[p.S] = C[u]; degree[p.F]--; C[p.F] -= C[u]; if(degree[p.F] == 1) Q.push(p.F); } } } // all remaining vertices should be disjoint cycles of odd length for(int i = 1; i <= n; i++) { if(degree[i] != 0 && degree[i] != 2) { cout << "0\n"; return 0; } } for(int i = 1; i <= n; i++) { if(degree[i] && !visited[i]) { vi comp; dfs(i, comp); if(comp.size() % 2 == 0) { cout << "0\n"; return 0; } ll sum = 0; for(int u : comp) sum += C[u]; sum /= 2; // keep edge cost between 0 and 1 for(int u = 2; u < comp.size(); u += 2) { sum -= C[comp[u]]; } ll last = 0; for(auto p : adj[comp[0]]) { if(p.F == comp[1]) { E[p.S] = sum; last = E[p.S]; } } for(int u = 1; u < comp.size(); u++) { for(auto p : adj[comp[u]]) { if(p.F == comp[(u+1)%comp.size()]) { E[p.S] = C[comp[u]]-last; last = E[p.S]; } } } } } for(int i = 0; i < m; i++) { cout << 2*E[i] << "\n"; } return 0; } /* 3 2 1 2 1 1 2 2 3 3 3 8 10 12 1 2 2 3 1 3 3 7 5 */

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:80:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for(int u = 2; u < comp.size(); u += 2) {
      |                            ~~^~~~~~~~~~~~~
pipes.cpp:90:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(int u = 1; u < comp.size(); u++) {
      |                            ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...