oj.uz

Submission #115414

# Submission time Handle Problem Language Result Execution time Memory
115414 2019-06-07T09:59:13 Z shashwatchandra Pipes (BOI13_pipes) C++17
74.0741 / 100
 357 ms 38648 KB 
/*input
4 3
-1
1
-3
1
1 2
1 3
1 4
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 1e5+1;
vector<pii> adj[N];
int n,m;
int c[N];
int now[N];
int dep[N];
vector<pii> edges;
map<pii,int> val;
bool works = 0;
bool vis[N];
int ans[5*N];
bool odd = 0;

void dfs(int u,int p,int ind = -1){
	if(vis[u])return;
	vis[u] = 1;
	for(auto v:adj[u]){
		if(!vis[v.f])dep[v.f] = dep[u]+1;
		else{
			if(v.f == p)continue;
			if(abs(dep[v.f]-dep[u])%2)odd = 1;
			else {
				//cout << u << " " << v << endl;
				ans[v.s] = 0;
			}
		}
		dfs(v.f,u,v.s);
	}
	if(p == -1){
		if(!odd)works = (now[u] == c[u]);
		return;
	}
	int diff = c[u]-now[u];
	//cout << u 3<< " " << diff << endl;
	now[p] += diff;
	ans[ind] = 2*diff;
	return;
}

void solve(){
  	cin >> n >> m;
  	RE(i,n)cin >> c[i];
  	RE(i,m){
  		int a,b;
  		cin >> a >> b;
  		adj[a].pb({b,i});
  		adj[b].pb({a,i});
  	}
  	dep[1] = 0;
  	dfs(1,-1);
  	if(odd or !works){
  		cout << 0 << endl;
  		return;
  	}
  	RE(i,m){
  		cout << ans[i] << "\n";
  	}
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2944 KB Output is correct
4 Correct 80 ms 11384 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 9 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 4 ms 2816 KB Output is correct
13 Correct 57 ms 9724 KB Output is correct
14 Correct 74 ms 10972 KB Output is correct
15 Correct 83 ms 11592 KB Output is correct
16 Correct 71 ms 10232 KB Output is correct
17 Correct 79 ms 11516 KB Output is correct
18 Correct 79 ms 11512 KB Output is correct
19 Correct 98 ms 13992 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2816 KB Output is correct
22 Correct 86 ms 11512 KB Output is correct
23 Correct 71 ms 9720 KB Output is correct
24 Correct 90 ms 11512 KB Output is correct
25 Correct 74 ms 10104 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 4 ms 2816 KB Output isn't correct
3 Correct 79 ms 12756 KB Output is correct
4 Correct 85 ms 14712 KB Output is correct
5 Correct 82 ms 11020 KB Output is correct
6 Correct 357 ms 38648 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Incorrect 4 ms 2688 KB Output isn't correct
9 Correct 8 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct
14 Incorrect 4 ms 2688 KB Output isn't correct
15 Incorrect 6 ms 2816 KB Output isn't correct
16 Incorrect 5 ms 2816 KB Output isn't correct
17 Correct 5 ms 2816 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 4 ms 2816 KB Output is correct
20 Correct 4 ms 2816 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Incorrect 5 ms 2816 KB Output isn't correct
23 Incorrect 94 ms 12024 KB Output isn't correct
24 Incorrect 95 ms 13560 KB Output isn't correct
25 Correct 81 ms 12688 KB Output is correct
26 Correct 103 ms 14380 KB Output is correct
27 Correct 99 ms 14456 KB Output is correct
28 Correct 119 ms 11384 KB Output is correct
29 Correct 312 ms 32576 KB Output is correct
30 Incorrect 94 ms 14968 KB Output isn't correct
31 Incorrect 97 ms 15228 KB Output isn't correct
32 Incorrect 80 ms 11768 KB Output isn't correct
33 Correct 86 ms 13688 KB Output is correct
34 Correct 85 ms 13816 KB Output is correct
35 Correct 91 ms 14712 KB Output is correct
36 Correct 87 ms 11256 KB Output is correct
37 Correct 354 ms 38532 KB Output is correct
38 Incorrect 87 ms 14584 KB Output isn't correct
39 Incorrect 76 ms 11644 KB Output isn't correct
40 Incorrect 86 ms 13408 KB Output isn't correct
41 Correct 84 ms 15224 KB Output is correct
42 Correct 85 ms 13944 KB Output is correct
43 Correct 98 ms 14840 KB Output is correct
44 Correct 84 ms 11132 KB Output is correct
45 Correct 256 ms 33156 KB Output is correct
46 Incorrect 91 ms 15484 KB Output isn't correct
47 Incorrect 83 ms 13560 KB Output isn't correct
48 Incorrect 83 ms 15096 KB Output isn't correct
49 Correct 71 ms 11256 KB Output is correct
50 Correct 85 ms 13816 KB Output is correct
51 Correct 92 ms 12536 KB Output is correct
52 Correct 92 ms 12252 KB Output is correct
53 Correct 300 ms 33212 KB Output is correct
54 Incorrect 81 ms 14200 KB Output isn't correct