oj.uz

Submission #111621

# Submission time Handle Problem Language Result Execution time Memory
111621 2019-05-15T18:49:04 Z wilwxk Pipes (BOI13_pipes) C++11
48.4889 / 100
 577 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];
ll v[MAXN], tenho[MAXN];
int gin[MAXN];
ll resp[MAXN], soma;
int n, m, tamcy;

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; tamcy++;
		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, %d)\n", cur, viz, ind, tenho[viz]);
		}
	}
}

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();

	if(m>n||tamcy%2==0) {
		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("%d\n", resp[i]);

}

Compilation message

pipes.cpp: In function 'void poda()':
pipes.cpp:18: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:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp:32: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:41: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:75:48: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  for(int i=1; i<=m; i++) printf("%d\n", resp[i]);
                                         ~~~~~~~^
pipes.cpp:52: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:53: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:55: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
9.6 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4992 KB Output isn't correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Incorrect 6 ms 5120 KB Output isn't correct
4 Incorrect 118 ms 14552 KB Output isn't correct
5 Incorrect 6 ms 4992 KB Output isn't correct
6 Incorrect 7 ms 5120 KB Output isn't correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Incorrect 8 ms 5120 KB Output isn't correct
9 Correct 6 ms 5120 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Incorrect 7 ms 5120 KB Output isn't correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 111 ms 12884 KB Output is correct
14 Correct 136 ms 14360 KB Output is correct
15 Correct 153 ms 14800 KB Output is correct
16 Correct 144 ms 13380 KB Output is correct
17 Incorrect 133 ms 14416 KB Output isn't correct
18 Incorrect 138 ms 14588 KB Output isn't correct
19 Incorrect 144 ms 14072 KB Output isn't correct
20 Incorrect 6 ms 5120 KB Output isn't correct
21 Incorrect 7 ms 5120 KB Output isn't correct
22 Incorrect 131 ms 14456 KB Output isn't correct
23 Correct 115 ms 12752 KB Output is correct
24 Incorrect 119 ms 14456 KB Output isn't correct
25 Correct 110 ms 13132 KB Output is correct

Subtask #2
38.8888888889 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 131 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 88 ms 13904 KB Output is correct
4 Correct 114 ms 14072 KB Output is correct
5 Correct 137 ms 14152 KB Output is correct
6 Runtime error 442 ms 43428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 107 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 7 ms 5036 KB Output isn't correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct
11 Correct 5 ms 5120 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 103 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 115 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Incorrect 7 ms 5120 KB Output isn't correct
17 Correct 7 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 6 ms 5120 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Runtime error 125 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Incorrect 80 ms 12496 KB Output isn't correct
24 Runtime error 543 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 110 ms 13936 KB Output is correct
26 Correct 139 ms 14200 KB Output is correct
27 Correct 102 ms 14072 KB Output is correct
28 Correct 102 ms 14328 KB Output is correct
29 Runtime error 303 ms 39540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 478 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Incorrect 108 ms 14160 KB Output isn't correct
32 Incorrect 128 ms 14408 KB Output isn't correct
33 Correct 102 ms 14360 KB Output is correct
34 Correct 123 ms 14184 KB Output is correct
35 Correct 126 ms 14172 KB Output is correct
36 Correct 120 ms 14200 KB Output is correct
37 Runtime error 434 ms 43520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 555 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 135 ms 14328 KB Output isn't correct
40 Runtime error 577 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 517 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 109 ms 14072 KB Output is correct
43 Correct 121 ms 14104 KB Output is correct
44 Correct 109 ms 14072 KB Output is correct
45 Correct 312 ms 18652 KB Output is correct
46 Runtime error 558 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 538 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 114 ms 14072 KB Output isn't correct
49 Correct 141 ms 13912 KB Output is correct
50 Correct 120 ms 14204 KB Output is correct
51 Correct 125 ms 14200 KB Output is correct
52 Correct 105 ms 14048 KB Output is correct
53 Correct 361 ms 18984 KB Output is correct
54 Runtime error 366 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)