QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108671 | #6335. Belt Conveyor | ikaurov | 25 | 1142ms | 41060kb | C++17 | 5.4kb | 2023-05-26 01:26:12 | 2023-05-26 01:26:16 |
Judging History
answer
#include "conveyor.h"
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
// #define endl '\n'
const int N = 1e5 + 20;
vector<int> g[N];
int found[N];
vector<int> active;
map<pair<int, int>, int> idx;
vector<int> lastquery, putball, nextdir, dir;
void setansdir(int u, int v){
int id, needdir;
if (idx.count(pair{u, v})){
id = idx[{u, v}], needdir = 0;
}
else if (idx.count(pair{v, u})) id = idx[{v, u}], needdir = 1;
else return;
if (dir[id] == -1){
dir[id] = needdir;
}
}
void setnextdir(int u, int v){
int id, needdir;
if (idx.count(pair{u, v})){
id = idx[{u, v}], needdir = 0;
}
else if (idx.count(pair{v, u})) id = idx[{v, u}], needdir = 1;
else return;
nextdir[id] = needdir ^ dir[id];
}
void setnextdir(int u, int v, int val){
if (idx.count(pair{u, v})) nextdir[idx[{u, v}]] = val;
if (idx.count(pair{v, u})) nextdir[idx[{v, u}]] = val;
}
void process1(vector<int> path){
if (sz(path) == 3){
putball[path[1]] = 1;
setnextdir(path[0], path[1], 0);
setnextdir(path[1], path[2], 0);
return;
}
int start = (sz(path) % 3 == 2? 2 : 1);
for (int i = start; i < sz(path) - 1; i += 3) putball[path[i]] = 1;
}
void process2(vector<int> path){
if (sz(path) == 3){
if (lastquery[path[1]]){
setansdir(path[0], path[1]);
setansdir(path[2], path[1]);
found[path[1]] = 1;
}
putball[path[1]] = 1;
setnextdir(path[0], path[1], 0);
setnextdir(path[1], path[2], 1);
return;
}
int start = (sz(path) % 3 == 2? 2 : 1);
for (int i = start; i < sz(path) - 1; i += 3){
if (lastquery[path[i]]){
setansdir(path[i - 1], path[i]);
setansdir(path[i + 1], path[i]);
}
else if ((i > 1 && lastquery[path[i - 1]]) || (i == 1 && !lastquery[path[i + 1]])){
setansdir(path[i], path[i - 1]);
setnextdir(path[i - 1], path[i]);
}
else{
setansdir(path[i], path[i + 1]);
setnextdir(path[i + 1], path[i]);
}
putball[path[i]] = 1;
}
}
void process3(vector<int> path){
if (sz(path) == 3){
if (lastquery[path[1]]){
setansdir(path[0], path[1]);
setansdir(path[1], path[2]);
found[path[1]] = 1;
}
putball[path[1]] = 1;
setnextdir(path[0], path[1], 1);
setnextdir(path[1], path[2], 0);
return;
}
int start = (sz(path) % 3 == 2? 2 : 1);
for (int i = start; i < sz(path) - 1; i += 3){
if (lastquery[path[i]]){
setansdir(path[i - 1], path[i]);
setansdir(path[i + 1], path[i]);
}
else if ((i > 1 && lastquery[path[i - 1]]) || (i == 1 && !lastquery[path[i + 1]])){
setansdir(path[i], path[i - 1]);
}
else{
setansdir(path[i], path[i + 1]);
}
setnextdir(path[i], path[i - 1]);
setnextdir(path[i], path[i + 1]);
}
for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
if (i) putball[path[i]] = 1;
else putball[path[i + 1]] = 1;
}
}
void process4(vector<int> path){
if (sz(path) == 3){
if (lastquery[path[1]]){
setansdir(path[1], path[0]);
setansdir(path[2], path[1]);
}
else if (!found[path[1]]){
setansdir(path[1], path[0]);
setansdir(path[1], path[2]);
}
}
else{
int start = (sz(path) % 3 == 2? 2 : 1);
for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
if (lastquery[path[i]]) setansdir(path[i + 1], path[i]);
else setansdir(path[i], path[i + 1]);
}
}
setnextdir(path[1], path[0]);
setnextdir(path.end()[-2], path.end()[-1]);
for (int i = 1; i < sz(path) - 1; i++) active[path[i]] = 0;
}
vector<vector<int>> paths;
vector<int> curpath;
void dfs1(int v, int p){
if (v != p) g[v].erase(find(all(g[v]), p));
for (auto u : g[v]){
dfs1(u, v);
}
}
void dfs2(int v, int p){
int c = 0;
for (auto u : g[v]){
c += active[u];
}
if (!active[v]){
goto end;
}
if (c <= 1){
if (curpath.empty()){
curpath.pb(p != v && active[p]? p : -1);
}
curpath.pb(v);
}
if (c == 0){
curpath.pb(-1);
if (sz(curpath) > 3 || curpath[0] != -1) paths.pb(curpath);
curpath.clear();
}
if (!curpath.empty() && p != v && p == curpath.back()){
curpath.pb(v);
paths.pb(curpath);
curpath.clear();
}
end: for (auto u : g[v]){
if (active[u]) dfs2(u, v);
}
for (auto u : g[v]){
if (!active[u]) dfs2(u, v);
}
}
void Solve(int n, std::vector<int> a, std::vector<int> b){
for (int i = 0; i < n - 1; i++){
idx[{a[i], b[i]}] = i;
g[a[i]].pb(b[i]);
g[b[i]].pb(a[i]);
}
active = vector<int>(n, 1);
putball = vector<int>(n, 0);
dir = vector<int>(n - 1, -1);
nextdir = vector<int>(n - 1, 0);
dfs1(0, 0);
while (1){
dfs2(0, 0);
if (paths.empty()) break;
for (auto p : paths) process1(p);
lastquery = Query(nextdir, putball);
fill(all(putball), 0);
for (auto p : paths) process2(p);
lastquery = Query(nextdir, putball);
fill(all(putball), 0);
for (auto p : paths) process3(p);
lastquery = Query(nextdir, putball);
fill(all(putball), 0);
for (auto p : paths) process4(p);
fill(all(putball), 0);
paths.clear();
}
Answer(dir);
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 5948kb
input:
random1 2 0 1 1 0xC321A02965AC2640
output:
Accepted: 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 4ms
memory: 6032kb
input:
random1 2 1 0 0 0x8A99AD9552B2C218
output:
Accepted: 3
result:
ok correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 6044kb
input:
random1 2 1 0 1 0x024D21FA307D148D
output:
Accepted: 3
result:
ok correct
Test #4:
score: 0
Accepted
time: 4ms
memory: 6016kb
input:
random1 2 0 1 0 0x3C96AB23CEB63F75
output:
Accepted: 3
result:
ok correct
Subtask #2:
score: 14
Accepted
Dependency #1:
100%
Accepted
Test #5:
score: 14
Accepted
time: 2ms
memory: 5972kb
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: 6
result:
ok correct
Test #6:
score: 0
Accepted
time: 4ms
memory: 6020kb
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: 5996kb
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: 2ms
memory: 5996kb
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: 3
result:
ok correct
Test #9:
score: 0
Accepted
time: 4ms
memory: 6076kb
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: 3
result:
ok correct
Test #10:
score: 0
Accepted
time: 4ms
memory: 6000kb
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: 6
result:
ok correct
Subtask #3:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 169ms
memory: 39592kb
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 #12:
score: 0
Accepted
time: 178ms
memory: 39564kb
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: 3
result:
ok correct
Test #13:
score: 0
Accepted
time: 176ms
memory: 41060kb
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: 176ms
memory: 39636kb
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: 3
result:
ok correct
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #15:
score: 0
Wrong Answer
time: 1142ms
memory: 32132kb
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:
Wrong Answer [5]
result:
wrong answer Token "Wrong" doesn't correspond to pattern "Accepted:"