// 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;
}
| # |
결과 |
실행 시간 |
메모리 |
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) |
| # |
결과 |
실행 시간 |
메모리 |
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) |
