oj.uz

답안 #555877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
555877 2022-05-01T18:33:33 Z blue Pipes (BOI13_pipes) C++17
65 / 100
 1000 ms 11652 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vll = vector<ll>;
#define sz(x) int(x.size())

const int mx = 100'000;

int N, M;
vpii edge[1+mx];
vll c(1+mx);


vll x(1+mx);

void dfs(int u, int p)
{
	for(pii vp : edge[u])
	{
		int v = vp.first;
		int e = vp.second;

		if(v == p) continue;
		dfs(v, u);

		x[e] = 2*c[v];

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

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

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

	if(M == N-1)
	{
		dfs(1, 0);
	}
	else
	{
		queue<int> tbv;
		vi visit(1+N, 0);

		vi deg(1+N);
		for(int i = 1; i <= N; i++)
		{
			deg[i] = sz(edge[i]);
			if(deg[i] == 1)
			{
				tbv.push(i);
				visit[i] = 1;
			}
		}

		// cerr << "A\n";


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

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

				if(visit[v]) continue;

				deg[v]--;

				x[e] = 2*c[v];
				c[v] -= c[u];
				c[u] = 0;

				if(!deg[v])
				{
					tbv.push(v);
					visit[v] = 1;
				}
			}
		}

		// cerr << "B\n";

		int U = 1;
		while(visit[U])
			U++;

		int viscount = 0;
		for(int u = 1; u <= N; u++)
			viscount += visit[u];

		vi edgevis(1+N, 0);

		// cerr << "C\n";

		while(1);

		vi nodes, edges;
		for(int z = 1; z <= N - viscount; z++)
		{
			for(auto vp : edge[U])
			{
				int v = vp.first;
				int e = vp.second;

				if(visit[v]) continue;
				if(edgevis[e]) continue;

				edgevis[e] = 1;


				nodes.push_back(U);
				edges.push_back(e);

				U = v;

				break;
			}
		}
		// cerr << "D\n";

		int Z = N - viscount;

		// cerr << "Z = " << Z << '\n';

		// for(int z = 0; z < Z; z++) cerr << nodes[z] << ' ' << edges[z] << '\n';

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

		vll a(Z), b(Z);
		a[0] = 1;
		b[0] = 0;

		for(int i = 1; i < Z; i++)
		{
			a[i] = -a[i-1];
			b[i] = c[nodes[i]] - b[i-1];
		}

		//(a.back() + a[0]) * x  +  (b.back() + b[0]) == c[nodes[0]]
		//x = (c[nodes[0]] - (b.back() + b[0])) / (a.back() + a[0])

		for(int i = 0; i < Z; i++)
		{
			x[edges[i]] = 2*((a[i] * (c[nodes[0]] - (b.back() + b[0]))) / (a.back() + a[0]) + b[i]);

			// cerr << i << " : " << nodes[i] << " : " << a[i] << ' ' << b[i] << "\n";
		}
	}

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 56 ms 8348 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 43 ms 7544 KB Output is correct
14 Correct 45 ms 8088 KB Output is correct
15 Correct 46 ms 8392 KB Output is correct
16 Correct 44 ms 7684 KB Output is correct
17 Correct 71 ms 8368 KB Output is correct
18 Correct 58 ms 8360 KB Output is correct
19 Correct 52 ms 11652 KB Output is correct
20 Correct 2 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 57 ms 8372 KB Output is correct
23 Correct 52 ms 7460 KB Output is correct
24 Correct 54 ms 8360 KB Output is correct
25 Correct 43 ms 7692 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 4180 KB Time limit exceeded
2 Execution timed out 1094 ms 4180 KB Time limit exceeded
3 Execution timed out 1093 ms 8744 KB Time limit exceeded
4 Correct 2 ms 4168 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Execution timed out 1086 ms 4180 KB Time limit exceeded
8 Execution timed out 1045 ms 4180 KB Time limit exceeded
9 Execution timed out 1093 ms 4180 KB Time limit exceeded
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 2 ms 4148 KB Output is correct
14 Execution timed out 1088 ms 4180 KB Time limit exceeded
15 Execution timed out 1075 ms 4180 KB Time limit exceeded
16 Execution timed out 1098 ms 4180 KB Time limit exceeded
17 Execution timed out 1091 ms 4180 KB Time limit exceeded
18 Correct 2 ms 4180 KB Output is correct
19 Correct 2 ms 4180 KB Output is correct
20 Correct 2 ms 4180 KB Output is correct
21 Correct 2 ms 4180 KB Output is correct
22 Execution timed out 1093 ms 4180 KB Time limit exceeded
23 Execution timed out 1099 ms 7924 KB Time limit exceeded
24 Execution timed out 1098 ms 8904 KB Time limit exceeded
25 Execution timed out 1100 ms 8788 KB Time limit exceeded
26 Correct 2 ms 4224 KB Output is correct
27 Correct 2 ms 4180 KB Output is correct
28 Correct 2 ms 4180 KB Output is correct
29 Correct 2 ms 4180 KB Output is correct
30 Execution timed out 1077 ms 8536 KB Time limit exceeded
31 Execution timed out 1082 ms 8612 KB Time limit exceeded
32 Execution timed out 1092 ms 9164 KB Time limit exceeded
33 Execution timed out 1100 ms 8816 KB Time limit exceeded
34 Correct 2 ms 4180 KB Output is correct
35 Correct 2 ms 4180 KB Output is correct
36 Correct 2 ms 4180 KB Output is correct
37 Correct 2 ms 4180 KB Output is correct
38 Execution timed out 1080 ms 8672 KB Time limit exceeded
39 Execution timed out 1090 ms 9164 KB Time limit exceeded
40 Execution timed out 1091 ms 8908 KB Time limit exceeded
41 Execution timed out 1095 ms 8528 KB Time limit exceeded
42 Correct 2 ms 4180 KB Output is correct
43 Correct 2 ms 4180 KB Output is correct
44 Correct 2 ms 4180 KB Output is correct
45 Correct 2 ms 4180 KB Output is correct
46 Execution timed out 1088 ms 8608 KB Time limit exceeded
47 Execution timed out 1060 ms 8908 KB Time limit exceeded
48 Execution timed out 1086 ms 8584 KB Time limit exceeded
49 Execution timed out 1069 ms 8956 KB Time limit exceeded
50 Correct 2 ms 4180 KB Output is correct
51 Correct 4 ms 4144 KB Output is correct
52 Correct 3 ms 4180 KB Output is correct
53 Correct 3 ms 4180 KB Output is correct
54 Execution timed out 1077 ms 8680 KB Time limit exceeded