Submission #677757

#TimeUsernameProblemLanguageResultExecution timeMemory
677757dooompyPipes (BOI13_pipes)C++17
72.78 / 100
148 ms17688 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; ll v[100005]; int deg[100005]; vector<pair<int, int>> adj[100005]; ll calc[500005]; bool seen[100005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; adj[a].push_back({b, i}); adj[b].push_back({a, i}); deg[a]++; deg[b]++; } queue<int> q; for (int i = 1; i <= n; i++) { if (deg[i] == 1) { q.push(i); } } while (!q.empty()) { // deg 1 auto cur = q.front(); q.pop(); seen[cur] = true; deg[cur] = 0; for (auto to : adj[cur]) { if (seen[to.first]) continue; ll weight = v[cur]; v[to.first] -= weight; calc[to.second] = weight; if (--deg[to.first] == 1) { q.push(to.first); } } } if (m == n - 1) { for (int i = 1; i <= m; i++) { cout << calc[i] * 2 << "\n"; } return 0; } if (m > n || m % 2 == 0) { cout << 0 << endl; return 0; } for (int i = 1; i <= n; i++) { assert(deg[i] == 2); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...