oj.uz

Submission #111640

# Submission time Handle Problem Language Result Execution time Memory
111640 2019-05-15T23:14:07 Z wilwxk Pipes (BOI13_pipes) C++11
74.0741 / 100
 500 ms 27496 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
vector<int> g[MAXN], lista[MAXN];
vector<int> ncyc;
ll v[MAXN], tenho[MAXN];
int gin[MAXN], marc[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];
			marc[ind]=1;
			tenho[viz]+=resp[ind];
			tenho[cur]+=resp[ind];
			// printf("%d -> %d (%d, %lld)\n", cur, viz, ind, tenho[cur]);
		}
	}
}

void dfs(int cur, int k) {
	// printf("%d %d\n", cur, k);
	gin[cur]=1;
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(gin[viz]!=2) continue;
		dfs(viz, k^1);
	}
	if(!k) soma+=v[cur];
	else soma-=v[cur];
}

void solve(int cur) {
	gin[cur]=2;
	// printf("solve %d\n", cur);
	for(int i=0; i<g[cur].size(); i++) {
		int viz=g[cur][i]; int ind=lista[cur][i];
		if(marc[ind]) continue;
		if(!tenho[cur]) resp[ind]=soma;
		else resp[ind]=v[cur]-tenho[cur];
		marc[ind]=1;
		tenho[viz]+=resp[ind];
		tenho[cur]+=resp[ind];
		// printf("%d -> %d (%d)\n", cur, viz, resp[ind]);
		solve(viz);
	}
}

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++) if(gin[i]) v[i]-=tenho[i], tenho[i]=0;
	// for(int i=1; i<=n; i++) cout << tenho[i] << " " << v[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, 0);	
		// printf("ok %lld\n", soma);
		solve(i);
		break;
	}

	bool ok=1;
	for(int i=1; i<=n; i++) if(gin[i]&&tenho[i]!=v[i]) ok=0;
	// for(int i=1; i<=n; i++) cout << tenho[i] << " " << v[i] << endl;

	if(ok) {
		for(int i=1; i<=m; i++) printf("%lld\n", resp[i]);
	}
	else {
		printf("0\n");
	}

}

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)':
pipes.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[cur].size(); i++) {
               ~^~~~~~~~~~~~~~
pipes.cpp:37:26: warning: unused variable 'ind' [-Wunused-variable]
   int viz=g[cur][i]; int ind=lista[cur][i];
                          ^~~
pipes.cpp: In function 'void solve(int)':
pipes.cpp:48: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:62: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:63: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:65: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 15 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 170 ms 20508 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 8 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 11 ms 9728 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 9 ms 9856 KB Output is correct
11 Correct 9 ms 9856 KB Output is correct
12 Correct 11 ms 9856 KB Output is correct
13 Correct 111 ms 18260 KB Output is correct
14 Correct 149 ms 19796 KB Output is correct
15 Correct 128 ms 20544 KB Output is correct
16 Correct 102 ms 19004 KB Output is correct
17 Correct 158 ms 20464 KB Output is correct
18 Correct 160 ms 20520 KB Output is correct
19 Correct 174 ms 20208 KB Output is correct
20 Correct 9 ms 9728 KB Output is correct
21 Correct 9 ms 9856 KB Output is correct
22 Correct 126 ms 20516 KB Output is correct
23 Correct 92 ms 18288 KB Output is correct
24 Correct 127 ms 20348 KB Output is correct
25 Correct 94 ms 18672 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9728 KB Output isn't correct
2 Incorrect 9 ms 9856 KB Output isn't correct
3 Correct 116 ms 19212 KB Output is correct
4 Correct 120 ms 19448 KB Output is correct
5 Correct 139 ms 19928 KB Output is correct
6 Correct 469 ms 27256 KB Output is correct
7 Incorrect 10 ms 9728 KB Output isn't correct
8 Incorrect 10 ms 9728 KB Output isn't correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Correct 12 ms 9728 KB Output is correct
14 Incorrect 13 ms 9856 KB Output isn't correct
15 Incorrect 10 ms 9856 KB Output isn't correct
16 Incorrect 10 ms 9856 KB Output isn't correct
17 Correct 11 ms 9856 KB Output is correct
18 Correct 11 ms 9856 KB Output is correct
19 Correct 11 ms 9856 KB Output is correct
20 Correct 10 ms 9856 KB Output is correct
21 Correct 11 ms 9856 KB Output is correct
22 Incorrect 10 ms 9856 KB Output isn't correct
23 Incorrect 132 ms 20148 KB Output isn't correct
24 Incorrect 176 ms 22232 KB Output isn't correct
25 Correct 123 ms 19192 KB Output is correct
26 Correct 129 ms 19452 KB Output is correct
27 Correct 131 ms 19192 KB Output is correct
28 Correct 132 ms 19852 KB Output is correct
29 Correct 298 ms 25620 KB Output is correct
30 Incorrect 130 ms 21640 KB Output isn't correct
31 Incorrect 161 ms 23416 KB Output isn't correct
32 Incorrect 141 ms 20720 KB Output isn't correct
33 Correct 127 ms 19720 KB Output is correct
34 Correct 115 ms 19456 KB Output is correct
35 Correct 146 ms 19476 KB Output is correct
36 Correct 195 ms 19832 KB Output is correct
37 Correct 500 ms 27496 KB Output is correct
38 Incorrect 184 ms 21728 KB Output isn't correct
39 Incorrect 129 ms 20352 KB Output isn't correct
40 Incorrect 161 ms 21872 KB Output isn't correct
41 Correct 102 ms 19320 KB Output is correct
42 Correct 127 ms 19192 KB Output is correct
43 Correct 92 ms 19192 KB Output is correct
44 Correct 138 ms 19800 KB Output is correct
45 Correct 369 ms 23644 KB Output is correct
46 Incorrect 182 ms 21332 KB Output isn't correct
47 Incorrect 203 ms 21948 KB Output isn't correct
48 Incorrect 160 ms 23252 KB Output isn't correct
49 Correct 143 ms 19624 KB Output is correct
50 Correct 142 ms 19704 KB Output is correct
51 Correct 138 ms 19716 KB Output is correct
52 Correct 125 ms 19236 KB Output is correct
53 Correct 399 ms 24372 KB Output is correct
54 Incorrect 167 ms 21176 KB Output isn't correct