Submission #84249

#	Time	Username	Problem	Language	Result	Execution time	Memory
84249		aome	Pipes (BOI13_pipes)	C++17	100 / 100	269 ms	30356 KiB

pipes

#include<bits/stdc++.h>
#define int long long
const int N = 1e5 + 5;
using namespace std;

typedef pair <int, int> ii;
vector <ii> adj[N];

int n, m, cnt[N], ans[5*N], a[N];
bool dead[N];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(ii(v, i));
        adj[v].push_back(ii(u, i));
        cnt[u]++; cnt[v]++;
    }
    queue <int> mq;
    for (int i = 1; i <= n; i++) if (cnt[i] <= 1) mq.push(i);
    while (mq.size()){
        int u = mq.front(); mq.pop();
        dead[u] = true;
        for (auto p : adj[u]){
            int v = p.first, id = p.second;
            cnt[v]--;
            if (dead[v]) continue;
            ans[id] = a[u]; a[v] -= a[u]; a[u] = 0;
            if (cnt[v] == 1) mq.push(v);
        }
        if (a[u]) return cout << 0, 0;
    }
    for (int i = 1; i <= n; i++) if (cnt[i] >= 3) return cout << 0, 0;
    for (int i = 1; i <= n; i++){
        if (dead[i]) continue;
        vector <ii> mv;
        int u = i, cnt = 0, cur = 0;
        while (!dead[u]){
            dead[u] = true; cnt++;
            for (auto p : adj[u]){
                int v = p.first, id = p.second;
                if (dead[v]) continue;
                ans[id] = a[u] - cur; cur = ans[id];
                u = v; mv.push_back(ii(u, id));
                break;
            }
        }
        for (auto p : adj[u]){
            int v = p.first, id = p.second;
            if (dead[v] && v != i) continue;
            ans[id] = a[u] - cur; cur = ans[id];
            u = v; mv.push_back(ii(u, id));
            break;
        }
        if (cnt % 2 == 0 || ans[mv.back().second] % 2 == 1) return cout << 0, 0;
        cur = ans[mv.back().second] / 2;
        for (int i = 0; i < mv.size(); i++) ans[mv[i].second] -= cur, cur = -cur;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] * 2 << "\n";
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < mv.size(); i++) ans[mv[i].second] -= cur, cur = -cur;
                         ~~^~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70