QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108660 | #6335. Belt Conveyor | ikaurov | Compile Error | / | / | C++17 | 4.5kb | 2023-05-25 22:30:25 | 2023-05-25 22:30:28 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-05-25 22:30:28]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-05-25 22:30:25]
- 提交
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'
vector<int> Query(vector<int> x, vector<int> y){
cout << "?" << endl;
for (auto i : x) cout << i << " ";
cout << endl;
for (auto i : y) cout << i << " ";
cout << endl;
vector<int> ans(sz(y));
for (auto &i : ans) cin >> i;
return ans;
}
void Answer(vector<int> x){
cout << "! ";
for (auto i : x) cout << i << " ";
cout << endl;
}
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);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout.precision(20);
int n;
cin >> n;
vector<int> a(n - 1), b(n - 1);
for (int i = 0; i < n - 1; i++) cin >> a[i] >> b[i];
Solve(n, a, b);
}
詳細信息
/usr/bin/ld: /tmp/ccI5WEsX.o: in function `Answer(std::vector<int, std::allocator<int> >)': answer.code:(.text+0x50): multiple definition of `Answer(std::vector<int, std::allocator<int> >)'; /tmp/cclBwudX.o:implementer.cpp:(.text+0x4d0): first defined here /usr/bin/ld: /tmp/ccI5WEsX.o: in function `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)': answer.code:(.text+0x2c0): multiple definition of `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/cclBwudX.o:implementer.cpp:(.text+0x670): first defined here /usr/bin/ld: /tmp/ccI5WEsX.o: in function `main': answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cclBwudX.o:implementer.cpp:(.text.startup+0x0): first defined here collect2: error: ld returned 1 exit status