QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67049 | #5015. 树 | Scapegoat_Dawn | 0 | 47ms | 54644kb | C++14 | 3.1kb | 2022-12-09 21:01:45 | 2022-12-09 21:01:48 |
Judging History
answer
#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c)) f |= (c == '-'), c = getchar();
while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
return f ? -x : x;
}
typedef vector <int> Vec;
random_device rd;
mt19937 Rng(time(0));
const int maxn = 2005, INF = 1e9 + 7;
int n, Root, Dep[maxn], D[maxn][maxn], Dist[maxn];
Vec Floor[maxn], G[maxn];
int ask(int u, vector<int> v);
void answer(int u, int v);
inline int Rand(int l, int r) { return Rng() % (r - l + 1) + l; }
inline void Add(int u, int v) {
G[u].emplace_back(v), G[v].emplace_back(u);
answer(u, v);
}
inline void Random_Shuffle(Vec &A, Vec &Point, Vec &Cnt, int Siz) {
for(register int i = 1; i < Cnt.size(); ++i) swap(Cnt[i], Cnt[Rng() % i]);
Siz = max(1, Rand(A.size() / 3, A.size() * 7 / 12));
for(register int i = 0; i < Siz; ++i) Cnt.emplace_back(A[i]);
}
inline int Dis_Sum(int x, Vec S) {
int Sum = 0;
for(int i : S) Sum += D[x][i];
return Sum;
}
inline void Search(int *Dis, int S) {
fill(Dis + 1, Dis + n + 1, INF);
queue <int> Q; Q.push(S), Dis[S] = 0;
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for(int y : G[x])
if(Dis[y] > Dis[x] + 1) {
Dis[y] = Dis[x] + 1;
Q.emplace(y);
}
}
}
inline bool cmp(int x, int y) { return Dist[x] < Dist[y]; }
inline void Solve(Vec A, Vec B) {
if(A.empty() || B.empty()) return ;
if(A.size() == 1) {
for(int i : B) Add(A[0], i);
return ;
}
if(B.size() == 1) {
for(int i : A)
if(ask(i, B) == 1) { Add(i, B[0]); break; }
return ;
}
Vec Point, Cnt = A; int Siz;
Random_Shuffle(A, Point, Cnt, Siz);
for(int i : A) Dist[i] = Dis_Sum(i, Point);
for(int i : B) Dist[i] = ask(i, Point);
sort(A.begin(), A.end(), cmp);
sort(B.begin(), B.end(), cmp);
vector < Vec > VecA, VecB;
int LA = 0, RA, LB = 0, RB = -1;
while(LA < A.size()) {
RA = LA;
while(RA + 1 < A.size() && Dist[A[RA + 1]] == Dist[A[LA]]) ++RA;
while(LB < B.size() && Dist[B[LB]] < Dist[A[LA]] + Point.size()) ++LB;
while(RB + 1 < B.size() && Dist[B[RB + 1]] <= Dist[A[LA]] + Point.size()) ++RB;
if(LB <= RB) {
Vec CntA, CntB;
for(register int i = LA; i <= RA; ++i) CntA.emplace_back(A[i]);
for(register int i = LB; i <= RB; ++i) CntB.emplace_back(B[i]);
VecA.emplace_back(CntA), VecB.emplace_back(CntB);
}
LA = RA + 1;
}
for(register int i = 0; i < VecA.size(); ++i) Solve(VecA[i], VecB[i]);
}
void solver(int _n, int A, int B) {
n = _n;
Root = Rand(1, n);
for(register int i = 1; i <= n; ++i) Dep[i] = ask(i, Vec(1, Root));
for(register int i = 1; i <= n; ++i) Floor[Dep[i]].emplace_back(i);
for(register int i = 0; i <= n; ++i) {
if(Floor[i].size() && Floor[i + 1].size()) Solve(Floor[i], Floor[i + 1]);
for(int j : Floor[i + 1]) Search(D[j], j);
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 47ms
memory: 54644kb
input:
1000 500000 500000 1 2 2 3 2 4 2 5 2 6 3 7 2 8 5 9 5 10 9 11 2 12 9 13 4 14 5 15 12 16 5 17 4 18 4 19 13 20 9 21 19 22 7 23 6 24 14 25 2 26 10 27 14 28 21 29 17 30 8 31 15 32 9 33 22 34 24 35 20 36 6 37 12 38 19 39 31 40 35 41 25 42 11 43 8 44 9 45 12 46 26 47 10 48 6 49 27 50 39 51 33 52 6 53 43 54...
output:
Too many queries
result:
wrong answer Wrong Answer
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 6236kb
input:
100 3000 40000 66 95 66 60 66 93 66 69 66 82 66 24 66 64 66 84 66 42 66 22 66 67 66 54 66 90 66 26 66 41 66 18 66 43 66 68 66 36 66 88 66 33 66 29 66 79 66 6 66 48 66 47 66 8 66 38 66 61 69 97 64 30 38 86 88 14 18 10 54 81 88 25 29 2 18 21 95 46 42 80 93 91 61 62 68 35 47 23 69 17 93 28 18 31 61 70 ...
output:
Too many queries
result:
wrong answer Wrong Answer
Subtask #3:
score: 0
Wrong Answer
Test #111:
score: 0
Wrong Answer
time: 26ms
memory: 24316kb
input:
1000 50000 3000000 126 207 937 126 615 937 837 615 500 837 588 500 505 588 353 505 60 353 904 60 656 904 685 656 460 685 614 460 551 614 537 551 858 537 596 858 9 596 738 9 918 738 322 918 940 322 859 940 113 859 110 113 312 110 995 312 443 995 246 443 257 246 238 257 999 238 885 999 976 885 330 976...
output:
Too many queries
result:
wrong answer Wrong Answer
Subtask #4:
score: 0
Wrong Answer
Test #211:
score: 0
Wrong Answer
time: 12ms
memory: 14780kb
input:
990 8500 300000 1 2 1 3 1 4 1 5 2 6 2 7 2 8 3 9 3 10 3 11 4 12 4 13 4 14 5 15 5 16 5 17 6 18 6 19 6 20 7 21 7 22 7 23 8 24 8 25 8 26 9 27 9 28 9 29 10 30 10 31 10 32 11 33 11 34 11 35 12 36 12 37 12 38 13 39 13 40 13 41 14 42 14 43 14 44 15 45 15 46 15 47 16 48 16 49 16 50 17 51 17 52 17 53 18 54 18...
output:
Too many queries
result:
wrong answer Wrong Answer