QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305371#6335. Belt Conveyordanielkou585525 207ms30176kbC++173.4kb2024-01-15 09:19:592024-01-15 09:19:59

Judging History

你现在查看的是最新测评结果

  • [2024-01-15 09:19:59]
  • 评测
  • 测评结果:25
  • 用时:207ms
  • 内存:30176kb
  • [2024-01-15 09:19:59]
  • 提交

answer

// Source: https://usaco.guide/general/io

#include "conveyor.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <bitset>

// #define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

const int inf = (int) 1e9;

vector<vector<pair<int, int>>> adj;

vector<int> idx, parent, edge_idx;

void dfs(int c, int p, int e) {
	parent[c] = p;
	edge_idx[c] = e;

	for (auto n : adj[c]) {
		if (n.first != p) {
			idx[n.first] = (idx[c] + 1) % 3;
			dfs(n.first, c, n.second);
		}
	}
}

pair<int, int> combine(const pair<int, int> &a, const pair<int, int> b) {
	if (b.first > a.first) {
		return b;
	}

	return a;
}

void Solve(int N, vector<int> arr, vector<int> brr) {
	adj.resize(N); idx.resize(N); parent.resize(N); edge_idx.resize(N);

	for (int i = 0; i < N - 1; i++) {
		adj[arr[i]].push_back({brr[i], i});
		adj[brr[i]].push_back({arr[i], i});
	}

	for (int i = 0; i < N; i++) {
		// start from leaf
		if (sz(adj[i]) == 1) {
			dfs(i, -1, -1); break;
		}
	}

	vector<int> ans(N - 1, inf); // inf means don't know

	while (true) {
		vector<int> ct(3, 0);

		pair<int, int> best = {0, 0};

		for (int i = 0; i < N; i++) {
			int tmp = 0;

			for (auto n : adj[i]) {
				tmp |= (ans[n.second] == inf);
			}

			if (tmp) {
				if (ct[idx[i]] == inf) {
					ct[idx[i]] = 0;
				} else if (ct[idx[i]] == 0) {
					ct[idx[i]]++;
				}
			}

			best = combine(best, make_pair(ct[idx[i]], idx[i]));
		}

		// query
		vector<int> xrr(N - 1, 0), yrr(N, 0);

		for (int i = 0; i < N; i++) {
			if (idx[i] == best.second) {
				yrr[i] = 1;
			}
		}

    	for (int i = 0; i < N; i++) {
      		if (yrr[i]) {
        		for (auto n : adj[i]) {
          			if (ans[n.second] == 0 && arr[n.second] == i) {
						xrr[n.second] = 1;
					}

          			if (ans[n.second] == 1 && brr[n.second] == i) {
						xrr[n.second] = 1;
					}
        		}
      		}
    	}

		vector<int> query = Query(xrr, yrr);

		for (int i = 0; i < N; i++) {
			if (!yrr[i]) {
				continue;
			}

			if (query[i]) {
				for (auto n : adj[i]) {
					if (xrr[n.second]) { // reversed
						if (n.first == brr[n.second]) {
							// a -> b reversed (b -> a) doesn't work
							ans[n.second] = 0;
						} else {
							// b -> a reversed (a -> b) doesn't work
							ans[n.second] = 1;
						}
					} else {
						// not reversed
						if (n.first == brr[n.second]) {
							// a -> b normal doesn't work
							ans[n.second] = 1;
						} else {
							// b -> a normal doesn't work
							ans[n.second] = 0;
						}
					}
				}
			} else {
				for (auto n : adj[i]) {
					if (query[n.first]) {
						if (xrr[n.second]) { // reversed
							if (n.first == brr[n.second]) {
								// a -> b reversed (b -> a) works
								ans[n.second] = 1;
							} else {
								// b -> a reversed (a -> b) works
								ans[n.second] = 0;
							}
						} else { // not reversed
							if (n.first == brr[n.second]) {
								// a -> b normal works
								ans[n.second] = 0;
							} else {
								// b -> a normal works
								ans[n.second] = 1;
							}
						}
					}
				}
			}
		}

		bool good = true;

		for (int i = 0; i < N - 1; i++) {
			if (ans[i] == inf) {
				good = false; break;
			}
		}

		if (good) {
			break;
		}
	}

	Answer(ans);
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 1ms
memory: 3672kb

input:

random1
2
0
1
1
0xC321A02965AC2640

output:

Accepted: 1

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

random1
2
1
0
0
0x8A99AD9552B2C218

output:

Accepted: 1

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

random1
2
1
0
1
0x024D21FA307D148D

output:

Accepted: 1

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

random1
2
0
1
0
0x3C96AB23CEB63F75

output:

Accepted: 1

result:

ok correct

Subtask #2:

score: 14
Accepted

Dependency #1:

100%
Accepted

Test #5:

score: 14
Accepted
time: 0ms
memory: 3632kb

input:

priority
30
10 29 10 13 17 11 2 15 15 27 9 26 18 0 14 1 22 24 29 28 6 22 4 20 15 5 28 4 21
24 3 13 1 8 13 12 8 19 16 3 1 10 24 29 12 8 4 7 2 7 28 25 12 7 2 23 27 22
89058848 6377689 24189123 31671827 205117644 254374430 56016068 6819602 212866321 246625321 274047319 230485311 202854776 280075001 203...

output:

Accepted: 5

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

random1
30
18 20 12 0 13 2 9 11 24 7 15 26 17 19 23 10 20 16 3 11 24 1 18 19 1 28 22 6 6
26 21 5 27 27 14 15 8 0 17 5 16 3 10 29 13 14 25 28 25 23 8 9 4 2 4 12 7 22
1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1
0x139BEEDAC0AE4AFB

output:

Accepted: 3

result:

ok correct

Test #7:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

priority
30
15 20 29 0 10 9 28 26 23 6 19 20 8 13 27 27 1 7 16 26 10 4 16 1 18 8 5 14 13
9 22 15 24 29 2 3 19 2 3 17 0 7 14 12 5 6 25 18 25 24 11 4 12 23 11 17 21 28
155983625 867841392 695948077 619352269 127722564 849426565 618649370 326405673 698896139 727112455 131828530 787535071 635627968 4725...

output:

Accepted: 3

result:

ok correct

Test #8:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

random1
30
11 11 11 11 23 20 11 11 11 26 11 21 11 11 11 27 11 11 11 16 13 17 5 11 11 1 11 14 11
24 28 10 3 11 11 22 25 8 11 29 11 12 15 9 11 19 0 2 11 11 11 11 18 4 11 7 11 6
0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1
0xD66348F4E914D783

output:

Accepted: 2

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

priority
30
1 7 19 19 21 3 16 25 19 2 4 19 19 22 19 19 27 18 19 24 19 19 19 19 19 19 19 19 28
19 19 29 0 19 19 19 19 15 19 19 10 5 19 6 14 19 19 23 19 8 11 9 26 17 12 13 20 19
175687064 613757478 145110402 817656856 712251185 850089290 510909115 900701092 956086121 136191567 90104148 72809899 345506...

output:

Accepted: 2

result:

ok correct

Test #10:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

priority
30
22 22 22 16 13 1 13 22 15 6 21 22 2 23 27 22 4 13 3 13 26 5 13 22 9 8 11 25 13
0 14 13 13 29 13 7 18 22 22 13 28 22 13 22 12 22 20 22 24 13 13 10 17 13 22 22 13 19
205508605 212446816 92507839 281454564 232828716 252753556 236784221 262865505 235145960 298570090 277536286 225110287 21565...

output:

Accepted: 2

result:

ok correct

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 71ms
memory: 28872kb

input:

random1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

Accepted: 5

result:

ok correct

Test #12:

score: 0
Accepted
time: 63ms
memory: 28968kb

input:

priority
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

Accepted: 5

result:

ok correct

Test #13:

score: 0
Accepted
time: 34ms
memory: 30176kb

input:

random1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

Accepted: 3

result:

ok correct

Test #14:

score: 0
Accepted
time: 74ms
memory: 29004kb

input:

priority
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

Accepted: 5

result:

ok correct

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #15:

score: 75
Accepted
time: 207ms
memory: 24572kb

input:

random1
100000
80421 79656 7373 22779 46143 23525 47891 79913 37297 20998 75128 48153 63344 14542 7176 46311 14404 86722 64420 35721 9418 16518 68787 60231 62713 24600 3621 36142 16253 35726 59248 8570 29713 29710 65003 65386 98313 32539 48464 79006 7464 99396 45447 11929 44648 44081 94041 40159 307...

output:

Accepted: 8

result:

ok correct

Test #16:

score: 0
Accepted
time: 161ms
memory: 24412kb

input:

random1
100000
47543 22001 16105 85619 83739 65453 81631 39199 45451 20382 85595 14410 39199 30963 55201 76378 25120 7516 39199 54202 40278 55022 44298 24421 18026 66509 33880 81569 24498 99677 49879 5902 76830 19128 34499 73731 32890 52171 54572 39199 91782 49370 45817 61462 23515 15408 40298 74640...

output:

Accepted: 7

result:

ok correct

Test #17:

score: -75
Wrong Answer
time: 190ms
memory: 24308kb

input:

random1
100000
54154 40864 51853 60873 46781 94584 40170 53625 38806 77573 2040 39786 34858 81565 80712 35628 88600 17657 29042 78470 12465 42107 99871 96640 83887 26160 67221 77210 16548 76907 36070 44287 83854 17095 84838 80345 84838 81932 77302 34933 63457 76048 85028 48884 95405 88687 84838 3426...

output:

Wrong Answer [8]

result:

wrong answer Token "Wrong" doesn't correspond to pattern "Accepted:"