제출 #59161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59161		Benq	Pipes (BOI13_pipes)	C++14	100 / 100	495 ms	22880 KiB

pipes

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

ll N,M,in[MX],c[MX],ans[MX];
bool done[MX];
vpi adj[MX];

template<int SZ> struct DSU {
    int par[SZ], sz[SZ], val[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) {
    	    val[x] ++;
    	    return 0;
    	}
    	if (sz[x] < sz[y]) swap(x,y);
    	val[x] ++;
    	sz[x] += sz[y], val[x] += val[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

vpi v;

void genCyc(int pre, int cur) {
    done[cur] = 1;
    for (auto a: adj[cur]) if (a.f != pre && !done[a.f]) {
        v.pb(a);
        genCyc(cur,a.f);
    }
}

ll cum[2*MX];

void solveCyc(int x) {
    v.clear(); 
    int pre = -1;
    for (auto y: adj[x]) if (!done[y.f]) {
        v.pb({x,y.s});
        pre = y.f;
        break;
    }
    genCyc(pre,x);
    if (sz(v) % 2 == 0) {
        cout << 0;
        exit(0);
    }
    ll sum = 0;
    for (auto a: v) sum += c[a.f];
    sum /= 2;
    
    F0R(i,2*sz(v)) {
        cum[i] = c[v[2*i%sz(v)].f];
        if (i) cum[i] += cum[i-1];
    }
    
    // v[1].s: {v[0].f,v[1].f}
    // v[3].s: {v[2].f,v[3].f}
    // 0: sum-(2+4+6+...+(N-1))
    F0R(i,sz(v)) {
        ans[v[i].s] = sum;
        int x = i+1; if (x&1) x += sz(v);
        // i+1, i+3, ..., i+N-2
        ans[v[i].s] += cum[x/2-1];
        ans[v[i].s] -= cum[(x+sz(v)-3)/2];
        // cout << "AH " << x << " " << sum << " " << cum[x/2-1] << " " << cum[(x+N-3)/2] << " " << ans[v[i].s] << "\n";
    }
    
    // cout << sz(v);
    // for (auto a: v) cout << a.f << " " << a.s << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    FOR(i,1,N+1) cin >> c[i];
    FOR(i,1,M+1) {
        int a,b; cin >> a >> b;
        adj[a].pb({b,i}), adj[b].pb({a,i});
        D.unite(a,b);
        in[a] ++, in[b] ++;
    }
    FOR(i,1,N+1) if (D.val[D.get(i)] > D.sz[D.get(i)]) {
        cout << 0;
        exit(0);
    }
    queue<int> q;
    FOR(i,1,N+1) if (in[i] == 1) q.push(i);
    while (sz(q)) {
        int x = q.front(); q.pop(); done[x] = 1;
        if (in[x] == 0) {
            // cout << x << "\n";
            continue;
        }
        for (auto a: adj[x]) if (!done[a.f]) {
            ans[a.s] = c[x];
            c[a.f] -= ans[a.s];
            in[a.f] --;
            if (in[a.f] == 1) q.push(a.f);
        }
    }
    FOR(i,1,N+1) if (!done[i]) {
        if (in[i] == 0) {
            done[i] = 1;
        } else solveCyc(i);
    }
    FOR(i,1,M+1) cout << 2*ans[i] << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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