oj.uz

Submission #518897

# Submission time Handle Problem Language Result Execution time Memory
518897 2022-01-25T04:46:56 Z blue Pipes (BOI13_pipes) C++17
65 / 100
 815 ms 23920 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9908 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 13 ms 9736 KB Output is correct
4 Correct 815 ms 16252 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 11 ms 9788 KB Output is correct
10 Correct 11 ms 9724 KB Output is correct
11 Correct 12 ms 9764 KB Output is correct
12 Correct 11 ms 9680 KB Output is correct
13 Correct 628 ms 14984 KB Output is correct
14 Correct 715 ms 15968 KB Output is correct
15 Correct 803 ms 16272 KB Output is correct
16 Correct 633 ms 15284 KB Output is correct
17 Correct 780 ms 16316 KB Output is correct
18 Correct 783 ms 16276 KB Output is correct
19 Correct 786 ms 15616 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 12 ms 9680 KB Output is correct
22 Correct 753 ms 16292 KB Output is correct
23 Correct 598 ms 14900 KB Output is correct
24 Correct 740 ms 16424 KB Output is correct
25 Correct 629 ms 15236 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 5 ms 9756 KB Output isn't correct
3 Incorrect 401 ms 14912 KB Output isn't correct
4 Correct 39 ms 13252 KB Output is correct
5 Correct 45 ms 13588 KB Output is correct
6 Correct 157 ms 23920 KB Output is correct
7 Incorrect 5 ms 9676 KB Output isn't correct
8 Incorrect 5 ms 9712 KB Output isn't correct
9 Incorrect 4 ms 9740 KB Output isn't correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 4 ms 9676 KB Output is correct
12 Correct 4 ms 9676 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Incorrect 5 ms 9724 KB Output isn't correct
15 Incorrect 5 ms 9676 KB Output isn't correct
16 Incorrect 9 ms 9736 KB Output isn't correct
17 Incorrect 8 ms 9728 KB Output isn't correct
18 Correct 5 ms 9732 KB Output is correct
19 Correct 5 ms 9740 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 5 ms 9804 KB Output is correct
22 Incorrect 9 ms 9736 KB Output isn't correct
23 Incorrect 265 ms 13620 KB Output isn't correct
24 Incorrect 400 ms 14872 KB Output isn't correct
25 Incorrect 459 ms 14816 KB Output isn't correct
26 Correct 49 ms 13344 KB Output is correct
27 Correct 50 ms 13264 KB Output is correct
28 Correct 48 ms 13636 KB Output is correct
29 Correct 149 ms 21264 KB Output is correct
30 Incorrect 460 ms 14436 KB Output isn't correct
31 Incorrect 148 ms 13792 KB Output isn't correct
32 Incorrect 699 ms 15792 KB Output isn't correct
33 Incorrect 406 ms 14680 KB Output isn't correct
34 Correct 48 ms 13252 KB Output is correct
35 Correct 47 ms 13260 KB Output is correct
36 Correct 45 ms 13552 KB Output is correct
37 Correct 175 ms 23824 KB Output is correct
38 Incorrect 558 ms 14612 KB Output isn't correct
39 Incorrect 779 ms 15904 KB Output isn't correct
40 Incorrect 508 ms 14900 KB Output isn't correct
41 Incorrect 142 ms 13776 KB Output isn't correct
42 Correct 46 ms 13204 KB Output is correct
43 Correct 49 ms 13224 KB Output is correct
44 Correct 45 ms 13568 KB Output is correct
45 Correct 157 ms 22340 KB Output is correct
46 Incorrect 551 ms 14608 KB Output isn't correct
47 Incorrect 465 ms 14764 KB Output isn't correct
48 Incorrect 174 ms 13812 KB Output isn't correct
49 Incorrect 725 ms 15512 KB Output isn't correct
50 Correct 56 ms 13364 KB Output is correct
51 Correct 44 ms 13228 KB Output is correct
52 Correct 38 ms 12868 KB Output is correct
53 Correct 156 ms 22108 KB Output is correct
54 Incorrect 536 ms 14432 KB Output isn't correct