QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125290 | #5014. 复读程度 | pandapythoner | Compile Error | / | / | C++14 | 5.5kb | 2023-07-16 14:52:56 | 2023-07-16 14:52:58 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-16 14:52:58]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-07-16 14:52:56]
- 提交
answer
#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(36346346);
const ll inf = 1e18;
#ifdef LOCAL
bool local = true;
#else
bool local = false;
#endif
void solve_aboba(vector<int> &a, int rt = -1, vector<int> dsts = {}){
int n = a.size();
if(n <= 1){
return;
}
if(n == 2){
answer(a[0], a[1]);
return;
}
int u, v;
int dst;
if(rt == -1){
auto gen_uv = [&](){
int u = a[rnd() % n];
int v = a[rnd() % n];
while(u == v){
v = a[rnd() % n];
}
return make_pair(ask(u, {v}), make_pair(u, v));
};
auto gd_uv = gen_uv();
if(n >= 25){
for(int itr = 0; itr < 6; itr += 1){
gd_uv = max(gd_uv, gen_uv());
}
}
dst = gd_uv.first;
auto uv = gd_uv.second;
u = uv.first;
v = uv.second;
} else{
u = rt;
auto gdv = make_pair(-1, -1);
for(int i = 0; i < n; i += 1){
gdv = max(gdv, make_pair(dsts[i], a[i]));
}
dst = gdv.first;
v = gdv.second;
if(dst == 1){
for(auto v: a){
if(v != rt){
answer(rt, v);
}
}
return;
}
}
vector<vector<int>> vrtcs(dst + 1);
vector<vector<int>> vdsts(dst + 1);
vrtcs[0].push_back(u);
vdsts[0].push_back(0);
vrtcs[dst].push_back(v);
vdsts[dst].push_back(0);
vector<int> base_vrtcs(dst + 1);
base_vrtcs[0] = u;
base_vrtcs[dst] = v;
for(int i = 0; i < n; i += 1){
if(a[i] == u || a[i] == v){
continue;
}
int x = a[i];
int dstu;
if(rt == -1){
dstu = ask(u, {x});
} else{
dstu = dsts[i];
}
int dstv = ask(v, {x});
ll dst_bbr = (dstu + dstv - dst) / 2;
ll rdstu = dstu - dst_bbr;
vrtcs[rdstu].push_back(x);
vdsts[rdstu].push_back(dst_bbr);
if(dst_bbr == 0){
base_vrtcs[rdstu] = x;
}
}
for(int i = 0; i < dst; i += 1){
answer(base_vrtcs[i], base_vrtcs[i + 1]);
}
for(int i = 0; i <= dst; i += 1){
solve_aboba(vrtcs[i], base_vrtcs[i], vdsts[i]);
}
}
int find_nxt(int v, vector<int> vrtcs, int d){
int n = vrtcs.size();
if(vrtcs.size() == 1){
return vrtcs[0];
}
int m = (n / 2);
vector<int> vl(vrtcs.begin(), vrtcs.begin() + m), vr(vrtcs.begin() + m, vrtcs.end());
int rs = -1;
if(ask(v, vl) == (d + 2) * m){
rs = find_nxt(v, vr, d);
} else{
rs = find_nxt(v, vl, d);
}
return rs;
}
void solve_fuck(vector<int> a){
int n = a.size();
int u = rnd() % n;
vector<vector<int>> f(n);
f[0].push_back(u);
vector<int> dsts(n);
dsts[u] = 0;
for(int v = 0; v < n; v += 1){
if(u == v){
continue;
}
int d = ask(a[u], {a[v]});
f[d].push_back(v);
dsts[v] = d;
}
vector<vector<int>> t(n);
vector<int> sz(n, 0);
vector<int> par(n, -1);
sz[u] = 1;
for(int md = 1; md < n; md += 1){
if(f[md].empty()){
break;
}
for(auto v: f[md]){
int prnt = u;
if(md > 1){
int q = u;
vector<int> usd(n, 0);
while(dsts[q] < md - 1){
if(!usd[q]){
int z = q;
vector<int> way = {z};
usd[z] = true;
while(!t[z].empty() && dsts[z] < md - 1){
pair<int, int> nxt = {-1, -1};
for(auto to: t[z]){
if(!usd[to]){
nxt = max(nxt, make_pair(sz[to], to));
}
}
if(nxt.first == -1){
break;
}
z = nxt.second;
way.push_back(z);
usd[z] = true;
}
int dstz = ask(a[v], {a[z]});
int dstlca = (dsts[z] + dsts[v] - dstz) / 2;
q = way[dstlca - dsts[q]];
} else{
vector<int> vrtcs;
for(auto to: t[q]){
if(!usd[to]){
vrtcs.push_back(to);
}
}
q = find_nxt(v, vrtcs, md - dsts[q] - 1);
}
}
prnt = q;
}
t[prnt].push_back(v);
par[v] = prnt;
int bbr = v;
while(bbr != -1){
sz[bbr] += 1;
bbr = par[bbr];
}
answer(a[v], a[prnt]);
}
}
}
void solver(int n, int A, int B){
vector<int> a(n);
for(int i = 0; i < n; i += 1){
a[i] = i + 1;
}
solve_fuck(a);
}
/*
7 1000 1000
1 2
2 3
1 4
1 5
5 6
4 7
*/
详细
answer.code:1:10: fatal error: tree.h: No such file or directory 1 | #include "tree.h" | ^~~~~~~~ compilation terminated.