oj.uz

Submission #518905

# Submission time Handle Problem Language Result Execution time Memory
518905 2022-01-25T05:21:58 Z blue Pipes (BOI13_pipes) C++17
90.9259 / 100
 171 ms 24128 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>;
#define sz(x) int(x.size())

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;

	vi node_visit(1+N, 0);

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

		node_visit[u] = 1;

		// 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 u = 1; u <= N; u++)
	// {
	// 	cerr << "node = " << u << '\n';
	// 	for(auto ed: edge[u]) cerr << ed.first << ' ' << ed.second << '\n';
	// }


	if(M == N)
	{
		// cerr << "done\n";
		ll a[1+N], b[1+N];

		int u = 1;
		while(node_visit[u]) u++;

		int src = u;

		vi edgelist;
		vi nodelist;

		while(1)
		{
			int nv = 0;
			for(auto ed: edge[u])
			{
				if(visit[ed.second]) continue;
				visit[ed.second] = 1;
				nv = 1;

				nodelist.push_back(u);
				edgelist.push_back(ed.second);

				// cerr << u << " -> " << ed.first << ' ' << ed.second << '\n';

				u = ed.first;
				break;
			}
			if(!nv) break;
		}

		int Z = sz(edgelist);

		a[0] = 1;
		b[0] = 0;

		if(Z % 2 == 0)
		{
			cout << "0\n";
			return 0;
		}

		for(int z = 0; z+1 < Z; z++)
		{
			a[z+1] = -a[z];
			b[z+1] = c[ nodelist[z+1] ] - b[z];
		}


		// for(int i = 0; i < Z; i++) cerr << nodelist[i] << ' ' << edgelist[i] << ' ' << a[i] << ' ' << b[i] << '\n';

		ll x = 0;

		//if(b[0] + b[z-1] != c[ nodelist[] ])
		if((b[0] + b[Z-1]) % 2 != c[nodelist[0]] % 2) 
		{
			cout << "0\n";
		}

		//x + b[0]  +  x + b[z-1]  ==  c[nodelist[0]]

		x = (c[nodelist[0]] - b[0] - b[Z-1]) / 2;

		for(int y = 0; y < Z; y++)
			ans[ edgelist[y] ] = 2 * (a[y] * x  +  b[y]);
	}




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

}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9676 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
4 Correct 57 ms 15052 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 4 ms 9736 KB Output is correct
7 Correct 5 ms 9732 KB Output is correct
8 Correct 5 ms 9708 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 5 ms 9716 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Correct 5 ms 9676 KB Output is correct
13 Correct 47 ms 14068 KB Output is correct
14 Correct 62 ms 14844 KB Output is correct
15 Correct 64 ms 15120 KB Output is correct
16 Correct 47 ms 14308 KB Output is correct
17 Correct 57 ms 15056 KB Output is correct
18 Correct 60 ms 15100 KB Output is correct
19 Correct 57 ms 14352 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Correct 5 ms 9740 KB Output is correct
22 Correct 56 ms 15036 KB Output is correct
23 Correct 53 ms 14132 KB Output is correct
24 Correct 63 ms 15112 KB Output is correct
25 Correct 53 ms 14272 KB Output is correct

Subtask #2
60.9259259259 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9728 KB Output isn't correct
2 Correct 4 ms 9676 KB Output is correct
3 Correct 64 ms 16068 KB Output is correct
4 Correct 46 ms 13560 KB Output is correct
5 Correct 48 ms 13764 KB Output is correct
6 Correct 171 ms 24120 KB Output is correct
7 Incorrect 4 ms 9724 KB Output isn't correct
8 Correct 4 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 4 ms 9676 KB Output is correct
11 Correct 4 ms 9652 KB Output is correct
12 Correct 4 ms 9628 KB Output is correct
13 Correct 4 ms 9676 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9804 KB Output is correct
16 Correct 5 ms 9676 KB Output is correct
17 Correct 5 ms 9808 KB Output is correct
18 Correct 5 ms 9680 KB Output is correct
19 Correct 5 ms 9740 KB Output is correct
20 Correct 5 ms 9744 KB Output is correct
21 Correct 5 ms 9720 KB Output is correct
22 Incorrect 5 ms 9740 KB Output isn't correct
23 Correct 47 ms 15288 KB Output is correct
24 Incorrect 61 ms 16296 KB Output isn't correct
25 Correct 47 ms 16052 KB Output is correct
26 Correct 41 ms 13656 KB Output is correct
27 Correct 45 ms 13444 KB Output is correct
28 Correct 62 ms 13872 KB Output is correct
29 Correct 118 ms 21572 KB Output is correct
30 Correct 59 ms 15932 KB Output is correct
31 Correct 57 ms 16452 KB Output is correct
32 Incorrect 67 ms 16620 KB Output isn't correct
33 Correct 50 ms 16292 KB Output is correct
34 Correct 37 ms 13520 KB Output is correct
35 Correct 45 ms 13624 KB Output is correct
36 Correct 50 ms 13808 KB Output is correct
37 Correct 161 ms 24128 KB Output is correct
38 Correct 59 ms 16176 KB Output is correct
39 Incorrect 69 ms 16516 KB Output isn't correct
40 Correct 66 ms 16436 KB Output is correct
41 Correct 52 ms 16344 KB Output is correct
42 Correct 42 ms 13404 KB Output is correct
43 Correct 50 ms 13504 KB Output is correct
44 Correct 59 ms 13828 KB Output is correct
45 Correct 134 ms 22664 KB Output is correct
46 Correct 63 ms 16104 KB Output is correct
47 Correct 59 ms 16408 KB Output is correct
48 Correct 61 ms 16416 KB Output is correct
49 Correct 47 ms 15948 KB Output is correct
50 Correct 53 ms 13740 KB Output is correct
51 Correct 41 ms 13856 KB Output is correct
52 Correct 39 ms 13480 KB Output is correct
53 Correct 133 ms 22268 KB Output is correct
54 Incorrect 64 ms 16000 KB Output isn't correct