oj.uz

Submission #115416

# Submission time Handle Problem Language Result Execution time Memory
115416 2019-06-07T10:06:13 Z shashwatchandra Pipes (BOI13_pipes) C++17
74.0741 / 100
 103 ms 15480 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;
  	if(m > n){
  		cout << 0;
  		return;
  	}
  	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 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 77 ms 11512 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 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 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 5 ms 2816 KB Output is correct
13 Correct 74 ms 9720 KB Output is correct
14 Correct 83 ms 11000 KB Output is correct
15 Correct 90 ms 11512 KB Output is correct
16 Correct 75 ms 10232 KB Output is correct
17 Correct 100 ms 11516 KB Output is correct
18 Correct 100 ms 11496 KB Output is correct
19 Correct 96 ms 13816 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2816 KB Output is correct
22 Correct 100 ms 11512 KB Output is correct
23 Correct 84 ms 9720 KB Output is correct
24 Correct 80 ms 11512 KB Output is correct
25 Correct 69 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 6 ms 2816 KB Output isn't correct
3 Correct 80 ms 12664 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 ms 2688 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 4 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 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 3 ms 2688 KB Output is correct
19 Correct 4 ms 2688 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Incorrect 4 ms 2816 KB Output isn't correct
23 Incorrect 65 ms 12040 KB Output isn't correct
24 Incorrect 85 ms 13560 KB Output isn't correct
25 Correct 83 ms 12788 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 4 ms 2688 KB Output is correct
28 Correct 3 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Incorrect 94 ms 15096 KB Output isn't correct
31 Incorrect 89 ms 15228 KB Output isn't correct
32 Incorrect 76 ms 11896 KB Output isn't correct
33 Correct 81 ms 13692 KB Output is correct
34 Correct 4 ms 2688 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 4 ms 2688 KB Output is correct
37 Correct 4 ms 2688 KB Output is correct
38 Incorrect 91 ms 14628 KB Output isn't correct
39 Incorrect 89 ms 11560 KB Output isn't correct
40 Incorrect 90 ms 13404 KB Output isn't correct
41 Correct 100 ms 15224 KB Output is correct
42 Correct 4 ms 2688 KB Output is correct
43 Correct 4 ms 2688 KB Output is correct
44 Correct 5 ms 2688 KB Output is correct
45 Correct 4 ms 2688 KB Output is correct
46 Incorrect 103 ms 15480 KB Output isn't correct
47 Incorrect 93 ms 13428 KB Output isn't correct
48 Incorrect 92 ms 15016 KB Output isn't correct
49 Correct 74 ms 11256 KB Output is correct
50 Correct 4 ms 2688 KB Output is correct
51 Correct 4 ms 2688 KB Output is correct
52 Correct 4 ms 2688 KB Output is correct
53 Correct 18 ms 2688 KB Output is correct
54 Incorrect 102 ms 14176 KB Output isn't correct