oj.uz

Submission #111623

# Submission time Handle Problem Language Result Execution time Memory
111623 2019-05-15T19:00:56 Z wilwxk Pipes (BOI13_pipes) C++11
59.2889 / 100
 627 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, %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||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
20.4 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 158 ms 15492 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 8 ms 5092 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Incorrect 7 ms 5120 KB Output isn't correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Incorrect 7 ms 5120 KB Output isn't correct
13 Incorrect 90 ms 13172 KB Output isn't correct
14 Incorrect 160 ms 14544 KB Output isn't correct
15 Incorrect 159 ms 15048 KB Output isn't correct
16 Incorrect 127 ms 13684 KB Output isn't correct
17 Correct 123 ms 15344 KB Output is correct
18 Correct 132 ms 15304 KB Output is correct
19 Correct 134 ms 15088 KB Output is correct
20 Correct 5 ms 5120 KB Output is correct
21 Correct 6 ms 5120 KB Output is correct
22 Correct 140 ms 15292 KB Output is correct
23 Incorrect 92 ms 13148 KB Output isn't correct
24 Correct 140 ms 15240 KB Output is correct
25 Incorrect 119 ms 13556 KB Output isn't correct

Subtask #2
38.8888888889 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 124 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 120 ms 14200 KB Output is correct
4 Correct 127 ms 14356 KB Output is correct
5 Correct 115 ms 14708 KB Output is correct
6 Runtime error 430 ms 43508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 118 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 6 ms 5120 KB Output isn't correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct
11 Correct 5 ms 5120 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 6 ms 5120 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 125 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 6 ms 5120 KB Output is correct
19 Correct 10 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 122 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Incorrect 106 ms 12764 KB Output isn't correct
24 Runtime error 627 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Correct 144 ms 14164 KB Output is correct
26 Correct 130 ms 14416 KB Output is correct
27 Correct 119 ms 14072 KB Output is correct
28 Correct 143 ms 14708 KB Output is correct
29 Runtime error 398 ms 39720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 484 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Incorrect 124 ms 14328 KB Output isn't correct
32 Incorrect 128 ms 15092 KB Output isn't correct
33 Correct 108 ms 14584 KB Output is correct
34 Correct 121 ms 14328 KB Output is correct
35 Correct 125 ms 14272 KB Output is correct
36 Correct 137 ms 14584 KB Output is correct
37 Runtime error 466 ms 43512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 608 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 138 ms 14920 KB Output isn't correct
40 Runtime error 520 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 541 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 102 ms 14200 KB Output is correct
43 Correct 110 ms 14020 KB Output is correct
44 Correct 104 ms 14808 KB Output is correct
45 Correct 257 ms 18636 KB Output is correct
46 Runtime error 457 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 410 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 90 ms 14200 KB Output isn't correct
49 Correct 102 ms 14520 KB Output is correct
50 Correct 133 ms 14584 KB Output is correct
51 Correct 152 ms 14652 KB Output is correct
52 Correct 149 ms 14168 KB Output is correct
53 Correct 309 ms 18964 KB Output is correct
54 Runtime error 549 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)