oj.uz

Submission #518895

# Submission time Handle Problem Language Result Execution time Memory
518895 2022-01-25T04:45:48 Z blue Pipes (BOI13_pipes) C++17
55.4 / 100
 1000 ms 29764 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;

const int mx = 100'000;
const int emx = 500'000;

vl c(1+mx);
vector<pii> edge[1+mx];

vi deg(1+mx, 0);
vi visit(1+emx, 0);

vector<ll> ans(1+emx);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N, M;
	cin >> N >> M;

	for(int i = 1; i <= N; i++) cin >> c[i];

	for(int j = 1; j <= M; j++)
	{
		int u, v;
		cin >> u >> v;
		edge[u].push_back({v, j});
		edge[v].push_back({u, j});
		deg[u]++;
		deg[v]++;
	}

	if(M > N)
	{
		cout << "0\n";
		return 0;
	}

	queue<int> tbv;
	for(int i = 1; i <= N; i++)
	{
		if(deg[i] == 1)
		{
			tbv.push(i);
		}
	}

	int endv = -1;

	while(!tbv.empty())
	{
		int u = tbv.front();
		tbv.pop();

		cerr << "u = " << u << '\n';

		int elim = 0;

		for(auto ed: edge[u])
		{
			int v = ed.first;

			if(visit[ed.second]) continue;

			visit[ed.second] = 1;

			deg[v]--;

			elim = 1;

			if(deg[v] <= 1)
			{
				tbv.push(v);
			}
			ans[ed.second] = 2*c[u];
			cerr << ed.first << ' ' << ed.second << " : " << 2*c[u] << '\n';

			c[v] -= c[u];
			c[u] -= c[u];

		}

		if(!elim)
		{
			if(M == N-1)
			{
				if(c[u] != 0)
				{
					cout << "0\n";
					return 0;
				}
			}
		}
	}


	for(int e = 1; e <= M; e++)
	{
		cout << ans[e] << '\n';
	}

}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:59:6: warning: unused variable 'endv' [-Wunused-variable]
   59 |  int endv = -1;
      |      ^~~~

Subtask #1
20.4 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 15 ms 9812 KB Output is correct
4 Execution timed out 1014 ms 17760 KB Time limit exceeded
5 Correct 7 ms 9728 KB Output is correct
6 Correct 6 ms 9720 KB Output is correct
7 Correct 7 ms 9732 KB Output is correct
8 Correct 6 ms 9724 KB Output is correct
9 Correct 14 ms 9748 KB Output is correct
10 Correct 14 ms 9796 KB Output is correct
11 Correct 15 ms 9800 KB Output is correct
12 Correct 15 ms 9804 KB Output is correct
13 Correct 872 ms 16656 KB Output is correct
14 Execution timed out 1022 ms 17976 KB Time limit exceeded
15 Execution timed out 1051 ms 17948 KB Time limit exceeded
16 Correct 957 ms 17096 KB Output is correct
17 Execution timed out 1057 ms 17716 KB Time limit exceeded
18 Execution timed out 1060 ms 18120 KB Time limit exceeded
19 Execution timed out 1065 ms 17236 KB Time limit exceeded
20 Correct 6 ms 9676 KB Output is correct
21 Correct 14 ms 9728 KB Output is correct
22 Execution timed out 1040 ms 17808 KB Time limit exceeded
23 Correct 906 ms 16708 KB Output is correct
24 Execution timed out 1047 ms 17952 KB Time limit exceeded
25 Correct 923 ms 16956 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9676 KB Output isn't correct
2 Incorrect 7 ms 9676 KB Output isn't correct
3 Incorrect 587 ms 16308 KB Output isn't correct
4 Correct 47 ms 14556 KB Output is correct
5 Correct 40 ms 14704 KB Output is correct
6 Correct 196 ms 29704 KB Output is correct
7 Incorrect 5 ms 9728 KB Output isn't correct
8 Incorrect 5 ms 9676 KB Output isn't correct
9 Incorrect 5 ms 9676 KB Output isn't correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 4 ms 9704 KB Output is correct
12 Correct 5 ms 9728 KB Output is correct
13 Correct 4 ms 9676 KB Output is correct
14 Incorrect 5 ms 9676 KB Output isn't correct
15 Incorrect 6 ms 9676 KB Output isn't correct
16 Incorrect 13 ms 9740 KB Output isn't correct
17 Incorrect 9 ms 9676 KB Output isn't correct
18 Correct 5 ms 9736 KB Output is correct
19 Correct 4 ms 9676 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 5 ms 9804 KB Output is correct
22 Incorrect 10 ms 9676 KB Output isn't correct
23 Incorrect 410 ms 14724 KB Output isn't correct
24 Incorrect 568 ms 16512 KB Output isn't correct
25 Incorrect 610 ms 16280 KB Output isn't correct
26 Correct 39 ms 14576 KB Output is correct
27 Correct 38 ms 14392 KB Output is correct
28 Correct 43 ms 14964 KB Output is correct
29 Correct 139 ms 25980 KB Output is correct
30 Incorrect 626 ms 16288 KB Output isn't correct
31 Incorrect 192 ms 15076 KB Output isn't correct
32 Incorrect 915 ms 17776 KB Output isn't correct
33 Incorrect 526 ms 16384 KB Output isn't correct
34 Correct 40 ms 14484 KB Output is correct
35 Correct 46 ms 14444 KB Output is correct
36 Correct 50 ms 14840 KB Output is correct
37 Correct 172 ms 29764 KB Output is correct
38 Incorrect 626 ms 16408 KB Output isn't correct
39 Incorrect 993 ms 18000 KB Output isn't correct
40 Incorrect 594 ms 16620 KB Output isn't correct
41 Incorrect 178 ms 15088 KB Output isn't correct
42 Correct 38 ms 14372 KB Output is correct
43 Correct 55 ms 14344 KB Output is correct
44 Correct 38 ms 14660 KB Output is correct
45 Correct 148 ms 27344 KB Output is correct
46 Incorrect 661 ms 16384 KB Output isn't correct
47 Incorrect 612 ms 16584 KB Output isn't correct
48 Incorrect 218 ms 15228 KB Output isn't correct
49 Incorrect 905 ms 17468 KB Output isn't correct
50 Correct 39 ms 14564 KB Output is correct
51 Correct 53 ms 14716 KB Output is correct
52 Correct 43 ms 14404 KB Output is correct
53 Correct 144 ms 27184 KB Output is correct
54 Incorrect 729 ms 16668 KB Output isn't correct