oj.uz

Submission #115413

# Submission time Handle Problem Language Result Execution time Memory
115413 2019-06-07T09:48:46 Z shashwatchandra Pipes (BOI13_pipes) C++17
67.5926 / 100
 1000 ms 67876 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 works = 0;
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){
		if(!odd)works = (now[u] == c[u]);
		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 or !works){
  		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 4 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 249 ms 23484 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 5 ms 2944 KB Output is correct
11 Correct 5 ms 2944 KB Output is correct
12 Correct 4 ms 2944 KB Output is correct
13 Correct 186 ms 19144 KB Output is correct
14 Correct 233 ms 22244 KB Output is correct
15 Correct 263 ms 23524 KB Output is correct
16 Correct 250 ms 20300 KB Output is correct
17 Correct 330 ms 23564 KB Output is correct
18 Correct 260 ms 23400 KB Output is correct
19 Correct 283 ms 26724 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 6 ms 2944 KB Output is correct
22 Correct 282 ms 23396 KB Output is correct
23 Correct 225 ms 19292 KB Output is correct
24 Correct 289 ms 23396 KB Output is correct
25 Correct 247 ms 19940 KB Output is correct

Subtask #2
37.5925925926 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2688 KB Output isn't correct
2 Incorrect 4 ms 2944 KB Output isn't correct
3 Correct 230 ms 25036 KB Output is correct
4 Correct 223 ms 28408 KB Output is correct
5 Correct 244 ms 22440 KB Output is correct
6 Execution timed out 1059 ms 66808 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 Correct 4 ms 2816 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 4 ms 2660 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct
14 Incorrect 4 ms 2688 KB Output isn't correct
15 Incorrect 5 ms 2944 KB Output isn't correct
16 Incorrect 6 ms 2944 KB Output isn't correct
17 Correct 5 ms 2944 KB Output is correct
18 Correct 6 ms 2944 KB Output is correct
19 Correct 5 ms 2944 KB Output is correct
20 Correct 6 ms 2944 KB Output is correct
21 Correct 6 ms 3200 KB Output is correct
22 Incorrect 5 ms 2944 KB Output isn't correct
23 Incorrect 176 ms 22984 KB Output isn't correct
24 Incorrect 218 ms 26852 KB Output isn't correct
25 Correct 204 ms 25160 KB Output is correct
26 Correct 215 ms 27620 KB Output is correct
27 Correct 241 ms 27988 KB Output is correct
28 Correct 250 ms 23652 KB Output is correct
29 Execution timed out 1051 ms 59344 KB Time limit exceeded
30 Incorrect 235 ms 28900 KB Output isn't correct
31 Incorrect 248 ms 29412 KB Output isn't correct
32 Incorrect 255 ms 24136 KB Output isn't correct
33 Correct 258 ms 26948 KB Output is correct
34 Correct 241 ms 27108 KB Output is correct
35 Correct 222 ms 28388 KB Output is correct
36 Correct 238 ms 23012 KB Output is correct
37 Execution timed out 1069 ms 67876 KB Time limit exceeded
38 Incorrect 247 ms 28440 KB Output isn't correct
39 Incorrect 233 ms 23652 KB Output isn't correct
40 Incorrect 256 ms 26468 KB Output isn't correct
41 Correct 254 ms 29276 KB Output is correct
42 Correct 242 ms 27240 KB Output is correct
43 Correct 235 ms 28924 KB Output is correct
44 Correct 226 ms 22444 KB Output is correct
45 Execution timed out 1056 ms 56912 KB Time limit exceeded
46 Incorrect 249 ms 29796 KB Output isn't correct
47 Incorrect 225 ms 26592 KB Output isn't correct
48 Incorrect 222 ms 29028 KB Output isn't correct
49 Correct 211 ms 22884 KB Output is correct
50 Correct 215 ms 26996 KB Output is correct
51 Correct 216 ms 25188 KB Output is correct
52 Correct 217 ms 24164 KB Output is correct
53 Execution timed out 1089 ms 59936 KB Time limit exceeded
54 Incorrect 234 ms 27620 KB Output isn't correct