oj.uz

Submission #111624

# Submission time Handle Problem Language Result Execution time Memory
111624 2019-05-15T19:03:20 Z wilwxk Pipes (BOI13_pipes) C++11
70.1852 / 100
 592 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e5+5;
vector<int> g[MAXN], lista[MAXN];
vector<int> ncyc;
ll v[MAXN], tenho[MAXN];
int gin[MAXN];
ll resp[MAXN], soma;
int n, m;

void poda() {
	queue<int> qu;
	for(int i=1; i<=n; i++) if(gin[i]==1) qu.push(i);
	while(!qu.empty()) {
		int cur=qu.front(); qu.pop();
		gin[cur]=0; ncyc.push_back(cur);
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; int ind=lista[cur][i];
			if(!gin[viz]) continue;
			gin[viz]--;
			if(gin[viz]<=1) qu.push(viz);
			resp[ind]=v[cur]-tenho[cur];
			tenho[viz]+=resp[ind];
			// printf("%d -> %d (%d, %lld)\n", cur, viz, ind, tenho[cur]);
		}
	}
}

void dfs(int cur, int p, int k) {
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(viz==p||gin[viz]==0) continue;
		dfs(viz, cur, k^1);
	}
	if(!k) soma+=tenho[cur];
	else soma-=tenho[cur];
}

void solve(int cur, int p) {
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(viz==p||gin[viz]==0) continue;
		if(cur==p) resp[ind]=soma;
		else resp[ind]=v[cur]-tenho[cur];
		tenho[viz]+=soma;
		solve(viz, cur);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%lld", &v[i]), v[i]*=2;
	for(int i=1; i<=m; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(b); g[b].push_back(a);
		gin[a]++; gin[b]++;
		lista[a].push_back(i); lista[b].push_back(i);
	}

	poda();
	// for(int i=1; i<=n; i++) cout << tenho[i] << endl;

	if(m>n||(n-ncyc.size())%2==0) {
		printf("0\n");
		return 0;
	}
	if(m==n-1&&tenho[ncyc.back()]!=v[ncyc.back()]) {
		printf("0\n");
		return 0;
	}

	for(int i=1; i<=n; i++) {
		if(!gin[i]) continue;
		dfs(i, i, 0);	
		solve(i, i);
		break;
	}

	for(int i=1; i<=m; i++) printf("%lld\n", resp[i]);

}

Compilation message

pipes.cpp: In function 'void poda()':
pipes.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs(int, int, int)':
pipes.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp:33:26: warning: unused variable 'ind' [-Wunused-variable]
   int viz=g[cur][i]; int ind=lista[cur][i];
                          ^~~
pipes.cpp: In function 'void solve(int, int)':
pipes.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:54:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", &v[i]), v[i]*=2;
                          ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
pipes.cpp:56:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 148 ms 15488 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 120 ms 13296 KB Output is correct
14 Correct 132 ms 14764 KB Output is correct
15 Correct 158 ms 15416 KB Output is correct
16 Correct 124 ms 14020 KB Output is correct
17 Correct 153 ms 15476 KB Output is correct
18 Correct 164 ms 15436 KB Output is correct
19 Correct 170 ms 15064 KB Output is correct
20 Correct 5 ms 4992 KB Output is correct
21 Correct 6 ms 5120 KB Output is correct
22 Correct 163 ms 15392 KB Output is correct
23 Correct 79 ms 13296 KB Output is correct
24 Correct 157 ms 15328 KB Output is correct
25 Correct 118 ms 13872 KB Output is correct

Subtask #2
40.1851851852 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 128 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 137 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 116 ms 14116 KB Output is correct
4 Correct 110 ms 14328 KB Output is correct
5 Correct 138 ms 14680 KB Output is correct
6 Runtime error 404 ms 43564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 101 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 111 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 7 ms 4992 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 5092 KB Output is correct
12 Correct 5 ms 4992 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Runtime error 98 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 111 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 118 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 6 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 7 ms 5120 KB Output is correct
20 Correct 8 ms 5120 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Runtime error 110 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 386 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 577 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 115 ms 14072 KB Output is correct
26 Correct 125 ms 14456 KB Output is correct
27 Correct 85 ms 14072 KB Output is correct
28 Correct 100 ms 14708 KB Output is correct
29 Runtime error 319 ms 39616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 579 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 581 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 429 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Correct 120 ms 14584 KB Output is correct
34 Correct 110 ms 14456 KB Output is correct
35 Correct 111 ms 14328 KB Output is correct
36 Correct 99 ms 14708 KB Output is correct
37 Runtime error 379 ms 43512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 581 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 366 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 571 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Correct 111 ms 14340 KB Output is correct
42 Correct 113 ms 14072 KB Output is correct
43 Correct 98 ms 14072 KB Output is correct
44 Correct 129 ms 14784 KB Output is correct
45 Correct 323 ms 18712 KB Output is correct
46 Runtime error 575 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 474 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 495 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Correct 118 ms 14516 KB Output is correct
50 Correct 118 ms 14584 KB Output is correct
51 Correct 103 ms 14560 KB Output is correct
52 Correct 156 ms 14228 KB Output is correct
53 Correct 362 ms 18984 KB Output is correct
54 Runtime error 592 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)