oj.uz

Submission #111622

# Submission time Handle Problem Language Result Execution time Memory
111622 2019-05-15T18:51:49 Z wilwxk Pipes (BOI13_pipes) C++11
48.4889 / 100
 622 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> cyc;
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; cyc.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, %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||cyc.size()%2==0) {
		printf("0\n");
		return 0;
	}
	if(m==n-1&&tenho[cyc.back()]!=v[cyc.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
9.6 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4992 KB Output isn't correct
2 Incorrect 6 ms 4992 KB Output isn't correct
3 Incorrect 6 ms 5120 KB Output isn't correct
4 Incorrect 114 ms 15120 KB Output isn't correct
5 Incorrect 5 ms 4992 KB Output isn't correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Incorrect 5 ms 4992 KB Output isn't correct
8 Incorrect 5 ms 5120 KB Output isn't correct
9 Correct 6 ms 5120 KB Output is correct
10 Incorrect 7 ms 5120 KB Output isn't correct
11 Incorrect 7 ms 5120 KB Output isn't correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 108 ms 13272 KB Output is correct
14 Correct 115 ms 14752 KB Output is correct
15 Correct 138 ms 15424 KB Output is correct
16 Correct 139 ms 13952 KB Output is correct
17 Incorrect 153 ms 15064 KB Output isn't correct
18 Incorrect 157 ms 15020 KB Output isn't correct
19 Incorrect 182 ms 14708 KB Output isn't correct
20 Incorrect 6 ms 4992 KB Output isn't correct
21 Incorrect 8 ms 5120 KB Output isn't correct
22 Incorrect 137 ms 15048 KB Output isn't correct
23 Correct 90 ms 13296 KB Output is correct
24 Incorrect 139 ms 14948 KB Output isn't correct
25 Correct 100 ms 13700 KB Output is correct

Subtask #2
38.8888888889 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 114 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 102 ms 14200 KB Output is correct
4 Correct 92 ms 14328 KB Output is correct
5 Correct 105 ms 14812 KB Output is correct
6 Runtime error 464 ms 43520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 112 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 6 ms 4992 KB Output isn't correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 24 ms 4992 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 5 ms 4992 KB Output is correct
14 Runtime error 101 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 126 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 6 ms 5120 KB Output is correct
18 Correct 6 ms 5120 KB Output is correct
19 Correct 7 ms 5120 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 7 ms 5248 KB Output is correct
22 Runtime error 124 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Incorrect 89 ms 12696 KB Output isn't correct
24 Runtime error 595 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 132 ms 14324 KB Output is correct
26 Correct 111 ms 14380 KB Output is correct
27 Correct 90 ms 14072 KB Output is correct
28 Correct 104 ms 14708 KB Output is correct
29 Runtime error 354 ms 39676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 442 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Incorrect 109 ms 14200 KB Output isn't correct
32 Incorrect 116 ms 15012 KB Output isn't correct
33 Correct 121 ms 14584 KB Output is correct
34 Correct 118 ms 14308 KB Output is correct
35 Correct 143 ms 14348 KB Output is correct
36 Correct 133 ms 14784 KB Output is correct
37 Runtime error 421 ms 43452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 494 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 121 ms 14908 KB Output isn't correct
40 Runtime error 622 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 566 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 113 ms 14016 KB Output is correct
43 Correct 109 ms 14004 KB Output is correct
44 Correct 127 ms 14748 KB Output is correct
45 Correct 376 ms 18680 KB Output is correct
46 Runtime error 492 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 476 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 117 ms 14316 KB Output isn't correct
49 Correct 144 ms 14516 KB Output is correct
50 Correct 117 ms 14584 KB Output is correct
51 Correct 152 ms 14656 KB Output is correct
52 Correct 124 ms 14200 KB Output is correct
53 Correct 335 ms 19020 KB Output is correct
54 Runtime error 543 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)