QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #347168 | #5015. 树 | zzafanti | 0 | 3ms | 7780kb | C++20 | 1.4kb | 2024-03-09 11:48:24 | 2024-03-09 11:48:25 |
answer
#include<bits/stdc++.h>
#include "tree.h"
using namespace std;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<int>> ver;
vector<pair<int,int>> ans;
vector<int> baned,fa;
void dfs(int u,int dep=1,vector<int> brother=vector<int>()){
vector<int> to;
for(auto p:ver[dep]){
if(fa[p]==u){
to.emplace_back(p);
continue;
}
if(baned[p]) continue;
int dis=ask(u,vector<int>(1,p));
if(dis==1){
ans.emplace_back(make_pair(u,p));
baned[p]=-1;
fa[p]=u;
to.emplace_back(p);
}
if(dis==3){
int l=0, r=brother.size()-1;
while(l<r){
int mid=(l+r)>>1;
vector<int> tmp;
for(int i=0; i<=mid; i++) tmp.emplace_back(brother[i]);
auto T=ask(p,tmp);
if(T==3*(mid+1)) l=mid+1;
else r=mid;
}
fa[p]=brother[l];
baned[p]=1;
}
}
shuffle(to.begin(),to.end(),gen);
for(auto p:to){
dfs(p,dep+1,to);
}
}
void solver(int n,int A,int B){
fa.resize(n+1),ver.resize(n+1); baned.resize(n+1);
int root=gen()%n+1;
for(int i=1; i<=n; i++){
int x=ask(root,vector<int>(1,i));
ver[x].emplace_back(i);
}
dfs(root);
assert(ans.size()==(n-1)*1u);
for(auto pt:ans){
//cerr<<pt.first<<' '<<pt.second<<endl;
answer(pt.first,pt.second);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
Unauthorized output
result:
Subtask #2:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
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:
Unauthorized output
result:
Subtask #3:
score: 0
Runtime Error
Test #111:
score: 0
Runtime Error
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:
Unauthorized output
result:
Subtask #4:
score: 0
Wrong Answer
Test #211:
score: 0
Wrong Answer
time: 3ms
memory: 7780kb
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