제출 #621359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
621359		353cerega	Pipes (BOI13_pipes)	C++17	74.07 / 100	122 ms	16284 KiB

pipes

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;





void solve()
{
    ll n, m;
    cin >> n >> m;
    if (m>n)
    {
        cout << 0 << "\n";
        return;
    }
    vector<ll> a(n);
    ll W = 0;
    for (ll i=0;i<n;i++)
    {
        cin >> a[i];
        W += a[i];
    }
    if (W%2!=0)
    {
        cout << 0 << "\n";
        return;
    }
    vector<ll> b(m), d(n);
    vector<pair<ll,ll>> e(m);
    vector<vector<ll>> g(n);
    for (ll i=0;i<m;i++)
    {
        ll u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(i);
        g[v].push_back(i);
        e[i] = {u,v};
        d[u]++, d[v]++;
    }
    vector<ll> was(m), ans(m);
    set<ll> kek;
    for (ll i=0;i<n;i++) if (d[i]==1) kek.insert(i);
    while (kek.size()>0)
    {
        ll u = *kek.begin();
        ll w = a[u];
        for (ll p: g[u])
        {
            if (was[p]==1) continue;
            was[p] = 1;
            d[e[p].X]--;
            if (d[e[p].X]==1) kek.insert(e[p].X);
            if (d[e[p].X]==0) kek.erase(e[p].X);
            d[e[p].Y]--;
            if (d[e[p].Y]==1) kek.insert(e[p].Y);
            if (d[e[p].Y]==0) kek.erase(e[p].Y);
            a[e[p].X] -= w;
            a[e[p].Y] -= w;
            ans[p] = w;
        }
    }
    ll D = 0;
    for (ll i=0;i<n;i++) if (d[i]==2) D++;
    if (D==0)
    {
        for (ll i=0;i<n;i++)
        {
            if (a[i]!=0)
            {
                cout << 0 << "\n";
                return;
            }
        }
        for (ll i=0;i<m;i++) cout << ans[i]*2 << "\n";
        return;
    }
    if (D%2==0)
    {
        cout << 0 << "\n";
        return;
    }
    for (ll st=0;st<n;st++)
    {
        if (d[st]!=2) continue;
        vector<ll> used(n);
        ll u = st;
        vector<ll> A, B;
        ll S = 0;
        for (ll k=0;k<D;k++)
        {
            A.push_back(a[u]);
            S += a[u];
            for (ll p: g[u])
            {
                if (was[p]==1) continue;
                was[p] = 1;
                B.push_back(p);
                u = u^e[p].X^e[p].Y;
                break;
            }
        }
        S /= 2;
        for (ll i=2;i<D;i+=2) S -= A[i];
        ll L = 0, R = D-1;
        ll Q = D;
        for (ll i=0;Q>0;i=(i+2)%D,Q--)
        {
            ans[B[i]] = S;
            L = (L+2)%D;
            S += A[L];
            R = (R+2)%D;
            S -= A[R];
        }
        for (ll i=0;i<m;i++) cout << ans[i] << "\n";
        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

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