oj.uz

Submission #115415

# Submission time Handle Problem Language Result Execution time Memory
115415 2019-06-07T10:04:10 Z shashwatchandra Pipes (BOI13_pipes) C++17
74.0741 / 100
 345 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];
int even = 0;
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;
				even++;
				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 or even > 1){
  		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 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 83 ms 11484 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 4 ms 2816 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 4 ms 2788 KB Output is correct
12 Correct 4 ms 2816 KB Output is correct
13 Correct 66 ms 9720 KB Output is correct
14 Correct 80 ms 11000 KB Output is correct
15 Correct 78 ms 11512 KB Output is correct
16 Correct 65 ms 10240 KB Output is correct
17 Correct 75 ms 11560 KB Output is correct
18 Correct 90 ms 11512 KB Output is correct
19 Correct 92 ms 13816 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2816 KB Output is correct
22 Correct 95 ms 11468 KB Output is correct
23 Correct 74 ms 9656 KB Output is correct
24 Correct 94 ms 11516 KB Output is correct
25 Correct 69 ms 10056 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 83 ms 12616 KB Output is correct
4 Correct 88 ms 14720 KB Output is correct
5 Correct 76 ms 11000 KB Output is correct
6 Correct 343 ms 38648 KB Output is correct
7 Incorrect 3 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 7 ms 2736 KB Output is correct
11 Correct 7 ms 2688 KB Output is correct
12 Correct 6 ms 2816 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 4 ms 2816 KB Output isn't correct
16 Incorrect 5 ms 2816 KB Output isn't correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 7 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 72 ms 12024 KB Output isn't correct
24 Incorrect 95 ms 13656 KB Output isn't correct
25 Correct 77 ms 12792 KB Output is correct
26 Correct 94 ms 14200 KB Output is correct
27 Correct 90 ms 14456 KB Output is correct
28 Correct 87 ms 11384 KB Output is correct
29 Correct 274 ms 32504 KB Output is correct
30 Incorrect 90 ms 14968 KB Output isn't correct
31 Incorrect 92 ms 15224 KB Output isn't correct
32 Incorrect 84 ms 11896 KB Output isn't correct
33 Correct 89 ms 13772 KB Output is correct
34 Correct 150 ms 13816 KB Output is correct
35 Correct 139 ms 14712 KB Output is correct
36 Correct 100 ms 11384 KB Output is correct
37 Correct 345 ms 38512 KB Output is correct
38 Incorrect 91 ms 14840 KB Output isn't correct
39 Incorrect 79 ms 11512 KB Output isn't correct
40 Incorrect 83 ms 13432 KB Output isn't correct
41 Correct 100 ms 15228 KB Output is correct
42 Correct 89 ms 14072 KB Output is correct
43 Correct 91 ms 14860 KB Output is correct
44 Correct 76 ms 10984 KB Output is correct
45 Correct 254 ms 33144 KB Output is correct
46 Incorrect 89 ms 15480 KB Output isn't correct
47 Incorrect 95 ms 13432 KB Output isn't correct
48 Incorrect 98 ms 14968 KB Output isn't correct
49 Correct 74 ms 11256 KB Output is correct
50 Correct 91 ms 13816 KB Output is correct
51 Correct 81 ms 12536 KB Output is correct
52 Correct 92 ms 12232 KB Output is correct
53 Correct 273 ms 33272 KB Output is correct
54 Incorrect 90 ms 14200 KB Output isn't correct