oj.uz

Submission #115411

# Submission time Handle Problem Language Result Execution time Memory
115411 2019-06-07T09:44:11 Z shashwatchandra Pipes (BOI13_pipes) C++17
42.963 / 100
 1000 ms 76060 KB 
/*input
4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3
*/
#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<int> adj[N];
int n,m;
int c[N];
int now[N];
int dep[N];
vector<pii> edges;
map<pii,int> val;
bool vis[N];
bool odd = 0;

void dfs(int u,int p){
	if(vis[u])return;
	vis[u] = 1;
	for(int v:adj[u]){
		if(!vis[v])dep[v] = dep[u]+1;
		else{
			if(v == p)continue;
			if(abs(dep[v]-dep[u])%2)odd = 1;
			else {
				//cout << u << " " << v << endl;
				val[{u,v}] = val[{v,u}] = 0;
			}
		}
		dfs(v,u);
	}
	if(p == -1)return;
	int diff = c[u]-now[u];
	//cout << u << " " << diff << endl;
	now[p] += diff;
	val[{u,p}] = 2*diff;
	val[{p,u}] = 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);
  		adj[b].pb(a);
  		edges.pb({a,b});
  	}
  	dep[1] = 0;
  	dfs(1,-1);
  	if(odd){
  		cout << 0 << endl;
  		return;
  	}
  	REP(i,m){
  		cout << val[edges[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 5 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 247 ms 24804 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 6 ms 2924 KB Output is correct
11 Correct 8 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 192 ms 20468 KB Output is correct
14 Correct 243 ms 23780 KB Output is correct
15 Correct 245 ms 24932 KB Output is correct
16 Correct 210 ms 21604 KB Output is correct
17 Correct 262 ms 24840 KB Output is correct
18 Correct 269 ms 25024 KB Output is correct
19 Correct 279 ms 28384 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 303 ms 25188 KB Output is correct
23 Correct 219 ms 20324 KB Output is correct
24 Correct 281 ms 24932 KB Output is correct
25 Correct 231 ms 21360 KB Output is correct

Subtask #2
12.962962963 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 5 ms 3072 KB Output isn't correct
3 Correct 255 ms 26552 KB Output is correct
4 Incorrect 286 ms 30572 KB Output isn't correct
5 Incorrect 259 ms 24392 KB Output isn't correct
6 Execution timed out 1063 ms 72556 KB Time limit exceeded
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Incorrect 4 ms 2688 KB Output isn't correct
9 Correct 4 ms 2688 KB Output is correct
10 Incorrect 5 ms 2688 KB Output isn't correct
11 Incorrect 4 ms 2688 KB Output isn't correct
12 Incorrect 4 ms 2688 KB Output isn't correct
13 Correct 5 ms 2816 KB Output is correct
14 Incorrect 5 ms 2688 KB Output isn't correct
15 Incorrect 5 ms 2944 KB Output isn't correct
16 Incorrect 5 ms 2944 KB Output isn't correct
17 Correct 5 ms 2944 KB Output is correct
18 Incorrect 5 ms 2944 KB Output isn't correct
19 Incorrect 5 ms 2944 KB Output isn't correct
20 Incorrect 5 ms 2944 KB Output isn't correct
21 Correct 6 ms 3120 KB Output is correct
22 Incorrect 5 ms 2944 KB Output isn't correct
23 Incorrect 221 ms 24620 KB Output isn't correct
24 Incorrect 254 ms 28848 KB Output isn't correct
25 Correct 208 ms 26600 KB Output is correct
26 Incorrect 237 ms 29668 KB Output isn't correct
27 Incorrect 254 ms 30032 KB Output isn't correct
28 Incorrect 265 ms 25692 KB Output isn't correct
29 Correct 997 ms 64868 KB Output is correct
30 Incorrect 230 ms 30844 KB Output isn't correct
31 Incorrect 236 ms 31252 KB Output isn't correct
32 Incorrect 246 ms 26212 KB Output isn't correct
33 Correct 267 ms 28500 KB Output is correct
34 Incorrect 271 ms 29156 KB Output isn't correct
35 Incorrect 258 ms 30436 KB Output isn't correct
36 Incorrect 249 ms 25028 KB Output isn't correct
37 Execution timed out 1080 ms 76060 KB Time limit exceeded
38 Incorrect 255 ms 30236 KB Output isn't correct
39 Incorrect 280 ms 25652 KB Output isn't correct
40 Incorrect 254 ms 28524 KB Output isn't correct
41 Correct 239 ms 31092 KB Output is correct
42 Incorrect 264 ms 29284 KB Output isn't correct
43 Incorrect 296 ms 30824 KB Output isn't correct
44 Incorrect 276 ms 24532 KB Output isn't correct
45 Execution timed out 1044 ms 61908 KB Time limit exceeded
46 Incorrect 285 ms 31912 KB Output isn't correct
47 Incorrect 276 ms 28744 KB Output isn't correct
48 Incorrect 259 ms 31076 KB Output isn't correct
49 Correct 234 ms 24292 KB Output is correct
50 Incorrect 285 ms 29132 KB Output isn't correct
51 Incorrect 273 ms 27108 KB Output isn't correct
52 Incorrect 301 ms 26212 KB Output isn't correct
53 Execution timed out 1074 ms 65556 KB Time limit exceeded
54 Incorrect 270 ms 29636 KB Output isn't correct