Submission #255617

#	Time	Username	Problem	Language	Result	Execution time	Memory
255617		shayan_p	Pipes (BOI13_pipes)	C++14	100 / 100	76 ms	13944 KiB

pipes

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

ll c[maxn], ans[maxn];
pll p[maxn];
int ID;

int tp[maxn], to[maxn], nxt[maxn];

void add_edge(int a, int b){
    static int C = 0;
    nxt[C] = tp[a], tp[a] = C, to[C] = b, C++;
}

int mark[maxn];

pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}

void dfs(int u, int par = -1){
    p[u].F = c[u];
    mark[u] = 1;
    for(int id = tp[u]; id != -1; id = nxt[id]){
	if(mark[to[id]] == 1 && to[id] != par){
	    if(ID == -1)
		ID = id >> 1;
	    if(ID != (id >> 1))
		cout << 0 << endl, exit(0);
	    p[u].S--;
	}
	else if(mark[to[id]] != 1){
	    dfs(to[id], u);
	    p[u]= p[u] - p[to[id]];
	}
    }
}
void go(int u){
    mark[u] = 2;
    for(int id = tp[u]; id != -1; id = nxt[id]){
	if(mark[to[id]] != 2){
	    go(to[id]);
	    ans[id >> 1] = p[to[id]].F + 1ll * (ID == -1 ? 0 : ans[ID]) * p[to[id]].S;
	}
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(tp, -1, sizeof tp);
    
    int n, m;
    cin >> n >> m;

    if(m > n)
	return cout << 0 << endl, 0;
    
    for(int i = 1; i <= n; i++){
	cin >> c[i];
    }
    for(int i = 0; i < m; i++){
	int a, b;
	cin >> a >> b;
	add_edge(a, b);
	add_edge(b, a);
    }
    for(int i = 1; i <= n; i++){
	if(mark[i] == 0){
	    ID = -1;
	    dfs(i);
	    if(ID == -1){
		if(! (p[i].F == 0 && p[i].S == 0) )
		    return cout << 0 << endl, 0;
	    }
	    else{
		if(p[i].S == 0)
		    return cout << 0 << endl, 0;
		if(p[i].F % p[i].S != 0)
		    return cout << 0 << endl, 0;
		ans[ID] = -(p[i].F / p[i].S);
	    }
	    go(i);
	}
    }
    for(int i = 0; i < m; i++){
	cout << 2ll * ans[i] << "\n";
    }
    return 0;
}

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