답안 #115412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115412 2019-06-07T09:46:30 Z shashwatchandra Pipes (BOI13_pipes) C++17
41.6667 / 100
1000 ms 69800 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){
		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;
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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)