oj.uz

Submission #111645

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

const int MAXN=5e5+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, int ori) {
	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(cur!=ori) 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, ori);
	}
}

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;
	}

	for(int i=1; i<=n; i++) {
		if(!gin[i]) continue;
		dfs(i, 0);	
		// printf("ok %lld\n", soma);
		solve(i, i);
		break;
	}

	bool ok=1;
	for(int i=1; i<=n; i++) if(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, 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 21 ms 23900 KB Output is correct
2 Correct 23 ms 23808 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 234 ms 34512 KB Output is correct
5 Correct 27 ms 23800 KB Output is correct
6 Correct 22 ms 23928 KB Output is correct
7 Correct 28 ms 24056 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 82 ms 23900 KB Output is correct
10 Correct 23 ms 23936 KB Output is correct
11 Correct 24 ms 23936 KB Output is correct
12 Correct 21 ms 23936 KB Output is correct
13 Correct 110 ms 32368 KB Output is correct
14 Correct 128 ms 34020 KB Output is correct
15 Correct 189 ms 34552 KB Output is correct
16 Correct 198 ms 33040 KB Output is correct
17 Correct 170 ms 34548 KB Output is correct
18 Correct 185 ms 34628 KB Output is correct
19 Correct 212 ms 34264 KB Output is correct
20 Correct 23 ms 23808 KB Output is correct
21 Correct 23 ms 23928 KB Output is correct
22 Correct 171 ms 34628 KB Output is correct
23 Correct 177 ms 32492 KB Output is correct
24 Correct 189 ms 34528 KB Output is correct
25 Correct 158 ms 32880 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Output isn't correct
2 Incorrect 24 ms 24024 KB Output isn't correct
3 Correct 128 ms 33280 KB Output is correct
4 Correct 128 ms 33548 KB Output is correct
5 Correct 150 ms 33880 KB Output is correct
6 Correct 397 ms 41376 KB Output is correct
7 Incorrect 24 ms 23808 KB Output isn't correct
8 Incorrect 25 ms 23936 KB Output isn't correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 20 ms 23808 KB Output is correct
11 Correct 22 ms 23808 KB Output is correct
12 Correct 23 ms 23896 KB Output is correct
13 Correct 22 ms 23896 KB Output is correct
14 Incorrect 22 ms 23964 KB Output isn't correct
15 Incorrect 23 ms 24036 KB Output isn't correct
16 Incorrect 25 ms 23936 KB Output isn't correct
17 Correct 24 ms 23928 KB Output is correct
18 Correct 24 ms 23940 KB Output is correct
19 Correct 22 ms 23928 KB Output is correct
20 Correct 26 ms 23928 KB Output is correct
21 Correct 27 ms 24056 KB Output is correct
22 Incorrect 20 ms 23936 KB Output isn't correct
23 Incorrect 141 ms 35072 KB Output isn't correct
24 Incorrect 166 ms 36952 KB Output isn't correct
25 Correct 134 ms 33452 KB Output is correct
26 Correct 113 ms 33528 KB Output is correct
27 Correct 117 ms 33244 KB Output is correct
28 Correct 180 ms 34040 KB Output is correct
29 Correct 449 ms 39968 KB Output is correct
30 Incorrect 214 ms 36300 KB Output isn't correct
31 Incorrect 215 ms 38904 KB Output isn't correct
32 Incorrect 190 ms 35112 KB Output isn't correct
33 Correct 153 ms 33940 KB Output is correct
34 Correct 155 ms 33528 KB Output is correct
35 Correct 129 ms 33516 KB Output is correct
36 Correct 122 ms 33860 KB Output is correct
37 Correct 487 ms 41540 KB Output is correct
38 Incorrect 187 ms 36644 KB Output isn't correct
39 Incorrect 138 ms 34576 KB Output isn't correct
40 Incorrect 193 ms 36764 KB Output isn't correct
41 Correct 124 ms 33480 KB Output is correct
42 Correct 131 ms 33308 KB Output is correct
43 Correct 146 ms 33400 KB Output is correct
44 Correct 161 ms 33968 KB Output is correct
45 Correct 366 ms 37788 KB Output is correct
46 Incorrect 200 ms 36184 KB Output isn't correct
47 Incorrect 189 ms 36924 KB Output isn't correct
48 Incorrect 232 ms 38696 KB Output isn't correct
49 Correct 142 ms 33716 KB Output is correct
50 Correct 197 ms 33924 KB Output is correct
51 Correct 165 ms 33760 KB Output is correct
52 Correct 136 ms 33400 KB Output is correct
53 Correct 397 ms 38328 KB Output is correct
54 Incorrect 179 ms 35896 KB Output isn't correct