| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 95218 |
2019-01-28T16:12:45 Z |
jangwonyoung |
Park (JOI17_park) |
C++14 |
|
160 ms |
832 KB |
#include "park.h"
#include<iostream>
#include<queue>
using namespace std;
#define pb push_back
//const int N=1401,M=1501;
int n;
vector<int>qry;
//int qar[1501];
vector<int>adj[1501];
vector<int>ds[1501];
int d[1501];
bool in[1501];
int tzuyu(int s,int e){
int qar[n];
for(int i=0; i<n ;i++) qar[i]=0;
for(auto cur:qry) qar[cur]=1;
if(s>e) swap(s,e);
int res=Ask(s,e,qar);
qry.clear();qry.shrink_to_fit();
return res;
}
void add(int x,int y){
adj[x].pb(y);adj[y].pb(x);
Answer(min(x,y),max(x,y));
}
vector<int>g;vector<int>h;
int bs(int s,int e){
int l=0,r=g.size()-1;
while(l!=r){
int mid=(l+r)/2;
for(auto cur:h) qry.pb(cur);
for(int i=0; i<=mid ;i++) qry.pb(g[i]);
int res=tzuyu(s,e);
if(res) r=mid;
else l=mid+1;
}
int res=g[l];
g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
return res;
}
void expand(int x,int y){
qry.pb(x);qry.pb(y);
if(tzuyu(x,y)){
d[y]=d[x]+1;ds[d[y]].pb(y);
add(x,y);
return;
}
h.pb(x);h.pb(y);
for(int i=0; i<n ;i++) if(!in[i]) g.pb(i);
int res=bs(x,y);
in[res]=true;
expand(x,res);expand(res,y);
}
void addtotree(int id){
for(int i=0; i<n ;i++) for(auto cur:ds[i]) g.pb(cur);//bfs order of some kind
for(int i=0; i<n ;i++) if(!in[i]) h.pb(i);
int boss=bs(0,id);in[id]=true;
expand(boss,id);
}
void init(){
ds[0].pb(0);
in[0]=true;
}
void Detect(int T, int N){
n=N;
init();
for(int i=1; i<n ;i++){
if(!in[i]) addtotree(i);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
632 KB |
Output is correct |
| 2 |
Correct |
155 ms |
632 KB |
Output is correct |
| 3 |
Correct |
122 ms |
664 KB |
Output is correct |
| 4 |
Correct |
60 ms |
632 KB |
Output is correct |
| 5 |
Correct |
59 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
504 KB |
Output is correct |
| 2 |
Correct |
157 ms |
604 KB |
Output is correct |
| 3 |
Correct |
158 ms |
640 KB |
Output is correct |
| 4 |
Correct |
151 ms |
644 KB |
Output is correct |
| 5 |
Correct |
152 ms |
504 KB |
Output is correct |
| 6 |
Correct |
152 ms |
632 KB |
Output is correct |
| 7 |
Correct |
156 ms |
632 KB |
Output is correct |
| 8 |
Correct |
160 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
544 KB |
Output is correct |
| 2 |
Correct |
129 ms |
612 KB |
Output is correct |
| 3 |
Correct |
128 ms |
832 KB |
Output is correct |
| 4 |
Correct |
106 ms |
604 KB |
Output is correct |
| 5 |
Correct |
98 ms |
632 KB |
Output is correct |
| 6 |
Correct |
113 ms |
760 KB |
Output is correct |
| 7 |
Correct |
73 ms |
636 KB |
Output is correct |
| 8 |
Correct |
120 ms |
676 KB |
Output is correct |
| 9 |
Correct |
100 ms |
500 KB |
Output is correct |
| 10 |
Correct |
126 ms |
632 KB |
Output is correct |
| 11 |
Correct |
115 ms |
764 KB |
Output is correct |
| 12 |
Correct |
125 ms |
632 KB |
Output is correct |
| 13 |
Correct |
74 ms |
612 KB |
Output is correct |
| 14 |
Correct |
132 ms |
764 KB |
Output is correct |
| 15 |
Correct |
76 ms |
632 KB |
Output is correct |
| 16 |
Correct |
157 ms |
504 KB |
Output is correct |
| 17 |
Correct |
60 ms |
636 KB |
Output is correct |
| 18 |
Correct |
127 ms |
604 KB |
Output is correct |
| 19 |
Correct |
70 ms |
680 KB |
Output is correct |
| 20 |
Correct |
108 ms |
616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
632 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
