QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108661 | #6335. Belt Conveyor | ikaurov | 0 | 0ms | 0kb | C++17 | 3.9kb | 2023-05-25 22:31:15 | 2023-05-25 22:31:16 |
Judging History
answer
#include "conveyor.h"
#include <bits/stdc++.h>
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];
vector<int> active;
map<pair<int, int>, int> idx;
vector<int> lastquery, putball, nextdir, dir;
void setansdir(int u, int v){
if (idx.count(pair{u, v})) dir[idx[{u, v}]] = 0;
if (idx.count(pair{v, u})) dir[idx[{v, u}]] = 1;
}
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 process1(vector<int> path){
int start = (sz(path) % 3 == 2? 1 : 0);
for (int i = start; i < sz(path) - 1; i += 3) putball[path[i]] = 1;
}
void process2(vector<int> path){
int start = (sz(path) % 3 == 2? 1 : 2);
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 (path[i - 1] != -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){
int start = (sz(path) % 3 == 2? 1 : 2);
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 (path[i - 1] != -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){
int start = (sz(path) % 3 == 2? 1 : 2);
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 (auto i : path) active[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 (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();
}
for (auto u : g[v]){
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, 0);
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);
}
Answer(dir);
}
詳細信息
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
random1 2 0 1 1 0xC321A02965AC2640
output:
Unauthorized output
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
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:
Unauthorized output
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%