Submission #255616

# Submission time Handle Problem Language Result Execution time Memory
255616 2020-08-01T12:39:24 Z shayan_p Pipes (BOI13_pipes) C++14
64.8593 / 100
55 ms 6272 KB
// 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 = 1e5 + 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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Runtime error 44 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Correct 1 ms 896 KB Output is correct
13 Incorrect 25 ms 3456 KB Output isn't correct
14 Runtime error 35 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 35 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 29 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 6012 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 44 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 55 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 1 ms 768 KB Output is correct
21 Correct 1 ms 768 KB Output is correct
22 Runtime error 35 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 28 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 38 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 28 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Runtime error 38 ms 6020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 896 KB Output is correct
16 Correct 1 ms 896 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 1 ms 768 KB Output is correct
19 Correct 1 ms 768 KB Output is correct
20 Correct 1 ms 768 KB Output is correct
21 Correct 1 ms 768 KB Output is correct
22 Correct 1 ms 896 KB Output is correct
23 Runtime error 29 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 46 ms 6012 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 36 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 1 ms 768 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 1 ms 768 KB Output is correct
30 Runtime error 36 ms 6084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 37 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 35 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 35 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 768 KB Output is correct
36 Correct 1 ms 768 KB Output is correct
37 Correct 1 ms 768 KB Output is correct
38 Runtime error 37 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 34 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Incorrect 35 ms 3836 KB Output isn't correct
41 Runtime error 35 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Correct 1 ms 768 KB Output is correct
43 Correct 1 ms 768 KB Output is correct
44 Correct 1 ms 768 KB Output is correct
45 Correct 1 ms 768 KB Output is correct
46 Runtime error 36 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 35 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 35 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Correct 29 ms 3712 KB Output is correct
50 Correct 1 ms 768 KB Output is correct
51 Correct 1 ms 768 KB Output is correct
52 Correct 1 ms 768 KB Output is correct
53 Correct 1 ms 768 KB Output is correct
54 Runtime error 33 ms 6008 KB Execution killed with signal 11 (could be triggered by violating memory limits)