QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305371 | #6335. Belt Conveyor | danielkou5855 | 25 | 207ms | 30176kb | C++17 | 3.4kb | 2024-01-15 09:19:59 | 2024-01-15 09:19:59 |
Judging History
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:"