Submission #115412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115412	2019-06-07T09:46:30 Z	shashwatchandra	Pipes (BOI13_pipes)	C++17	41.6667 / 100	1000 ms	69800 KB

pipes

/*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){
		if(!odd)assert(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){
  		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	243 ms	23500 KB	Output is correct
5	Correct	3 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	4 ms	2944 KB	Output is correct
11	Correct	4 ms	2944 KB	Output is correct
12	Correct	5 ms	2944 KB	Output is correct
13	Correct	193 ms	19272 KB	Output is correct
14	Correct	242 ms	22372 KB	Output is correct
15	Correct	251 ms	23660 KB	Output is correct
16	Correct	203 ms	20452 KB	Output is correct
17	Correct	277 ms	23548 KB	Output is correct
18	Correct	244 ms	23524 KB	Output is correct
19	Correct	265 ms	26824 KB	Output is correct
20	Correct	4 ms	2688 KB	Output is correct
21	Correct	5 ms	2944 KB	Output is correct
22	Correct	239 ms	23588 KB	Output is correct
23	Correct	184 ms	19300 KB	Output is correct
24	Correct	262 ms	23652 KB	Output is correct
25	Correct	194 ms	20156 KB	Output is correct

Subtask #2

11.6666666667 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	7 ms	5248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	8 ms	5888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Correct	204 ms	25188 KB	Output is correct
4	Runtime error	231 ms	56896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	245 ms	44900 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Execution timed out	1079 ms	67516 KB	Time limit exceeded
7	Runtime error	8 ms	5376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	7 ms	5376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	4 ms	2688 KB	Output is correct
10	Runtime error	8 ms	5348 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	7 ms	5376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	7 ms	5376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	4 ms	2816 KB	Output is correct
14	Runtime error	9 ms	5248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	9 ms	5888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	5 ms	2944 KB	Output is correct
18	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Correct	6 ms	3200 KB	Output is correct
22	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	171 ms	45924 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	211 ms	53608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Correct	218 ms	25308 KB	Output is correct
26	Runtime error	251 ms	55268 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	248 ms	56036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	256 ms	47076 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Execution timed out	1050 ms	60016 KB	Time limit exceeded
30	Runtime error	215 ms	57828 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	219 ms	58472 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	207 ms	48228 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Correct	228 ms	27108 KB	Output is correct
34	Runtime error	222 ms	53900 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	249 ms	56804 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	244 ms	45924 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Execution timed out	1073 ms	69800 KB	Time limit exceeded
38	Runtime error	210 ms	56604 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	203 ms	47204 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	231 ms	52928 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Correct	239 ms	29416 KB	Output is correct
42	Runtime error	218 ms	54632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	254 ms	57628 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	262 ms	44908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Execution timed out	1074 ms	57044 KB	Time limit exceeded
46	Runtime error	248 ms	59760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	251 ms	53312 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	231 ms	58048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Correct	200 ms	23016 KB	Output is correct
50	Runtime error	210 ms	53988 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	221 ms	50276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	211 ms	48328 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Execution timed out	1066 ms	60164 KB	Time limit exceeded
54	Runtime error	241 ms	55012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)