Submission #950509

#	Time	Username	Problem	Language	Result	Execution time	Memory
950509		phoenix0423	Pipes (BOI13_pipes)	C++17	100 / 100	128 ms	52000 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 5e5 + 5;
int n, m;
vector<pll> adj[maxn];
int ans[maxn], val[maxn], deg[maxn];

void dfs(int pos, int prev){
    for(auto [x, id] : adj[pos]){
        if(x == prev) continue;
        dfs(x, pos);
        ans[id] = val[x], val[pos] -= val[x];
    }
}

signed main(void){
    fastio;
    cin>>n>>m;
    for(int i = 0; i < n; i++) cin>>val[i];
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].eb(b, i);
        adj[b].eb(a, i);
        deg[a] ++, deg[b] ++;
    }
    if(m > n){
        cout<<0<<"\n";
        return 0; 
    }
    queue<int> q;
    for(int i = 0; i < n; i++) if(deg[i] == 1) q.push(i);
    while(!q.empty()){
        int pos = q.front(); q.pop();
        deg[pos] = 0;
        for(auto [x, id] : adj[pos]){
            if(!deg[x]) continue;
            ans[id] = val[pos], val[x] -= val[pos];
            deg[x] --;
            if(deg[x] == 1) q.push(x);
        }
    }
    if(m == n - 1){
        for(int i = 0; i < m; i++) cout<<ans[i] * 2<<"\n";
        return 0;
    }
    int st = 0;
    for(int i = 0; i < n; i++){
        if(deg[i] == 2){
            st = i;
            break;
        }
    }
    int len = 0;
    vector<int> vis(n);
    vector<int> cyc;
    while(!vis[st]){
        vis[st] = 1;
        cyc.pb(st);
        for(auto [x, id] : adj[st]){
            if(!vis[x] && deg[x] == 2){
                st = x;
                break;
            }
        }
    }
    if(cyc.size() % 2 == 0){
        cout<<0<<"\n";
        return 0;
    }
    int ttl = 0;
    for(int i = 1; i < cyc.size(); i++){
        ttl += val[cyc[i]] * (i % 2 ? 1 : -1);
    }
    int a = (ttl + val[cyc[0]]) / 2;
    for(int i = 0; i < cyc.size(); i++){
        for(auto [x, id] : adj[cyc[i]]){
            if(x != cyc[(i + 1) % cyc.size()]) continue;
            ans[id] = a;
            a = val[x] - a;
        }
    }
    for(int i = 0; i < m; i++) cout<<ans[i] * 2<<"\n";
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:81:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 1; i < cyc.size(); i++){
      |                    ~~^~~~~~~~~~~~
pipes.cpp:85:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < cyc.size(); i++){
      |                    ~~^~~~~~~~~~~~
pipes.cpp:63:9: warning: unused variable 'len' [-Wunused-variable]
   63 |     int len = 0;
      |         ^~~

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