| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594583 |
2022-07-12T17:20:34 Z |
Koosha_mv |
Park (JOI17_park) |
C++14 |
|
433 ms |
732 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1505;
mt19937 rng(time(nullptr));
int n,par[N],vis[N],mark[N],place[N];
vector<int> g[N];
void reset(){
f(i,0,n) place[i]=0;
}
int rand(int l,int r){
uniform_int_distribution<int> rnd(l,r-1);
return rnd(rng);
}
int ask(int s,int t){
if(s>t) swap(s,t);
int res=Ask(s,t,place);
return res;
}
void path(int s,int t,vector<int> vec){
if(vec.size()==0){
if(s>t) swap(s,t);
cout<<s<<" -> "<<t<<endl;
Answer(s,t);
g[s].pb(t);
g[t].pb(s);
return ;
}
int id=vec[rand(0,vec.size())];
reset();
place[s]=place[t]=1;
for(auto x : vec){
place[x]=1;
}
vector<int> L,R;
for(auto x : vec){
if(x==id) continue ;
place[x]=0;
if(ask(s,id)==0) L.pb(x);
else R.pb(x);
place[x]=1;
}
path(s,id,L);
path(id,t,R);
}
void dfs1(int u,int p,vector<int> &vec){
vis[u]=1;
par[u]=p;
vec.pb(u);
for(auto v : g[u]){
if(v==p || vis[v]) continue ;
par[u]=v;
dfs1(v,u,vec);
}
}
void solve(int x,int u){
vector<int> vec;
dfs1(u,u,vec);
reset();
place[x]=1;
for(auto i : vec) place[i]=1;
if(ask(x,vec[0])==0) return ;
int l=0,r=vec.size();
while(l+1<r){
int mid=(l+r)>>1;
f(i,0,vec.size()) place[vec[i]]=(i<mid);
if(ask(x,vec[0])==1) r=mid;
else l=mid;
}
vis[vec[l]]=1;
for(auto i : g[vec[l]]){
if(vis[i]==1 || par[vec[l]]==i) continue ;
solve(x,i);
}
if(l>0){
solve(x,u);
}
Answer(min(x,vec[l]),max(x,vec[l]));
}
void do_it(int x){
for(auto u : g[x]){
vis[u]=1;
for(auto v : g[u]){
if(v==x) continue ;
solve(x,v);
}
}
}
void Detect(int T, int _n) {
n=_n;
mark[0]=1;
vector<int> B(1);
f(i,1,n){
if(mark[i]) continue ;
vector<int> vec,A;
mark[i]=1;
f(j,0,n) if(!mark[j]) A.pb(j);
int l=-1,r=A.size();
while(1){
while(l+1<r){
int mid=(l+r)>>1;
reset();
vector<int> p;
fill(vis,vis+n,0);
dfs1(0,0,p);
place[0]=place[i]=1;
for(auto x : p) place[x]=1;
f(j,0,mid) place[A[j]]=1;
f(j,mid,A.size()) place[A[j]]=mark[A[j]];
if(ask(0,i)==0){
l=mid;
}
else{
r=mid;
}
}
if(l==-1) break;
mark[A[l]]=1;
vec.pb(A[l]);
r=l,l=-1;
}
reset();
vector<int> p;
fill(vis,vis+n,0);
dfs1(0,0,p);
place[i]=1;
for(auto x : vec) place[x]=1;
l=0,r=p.size();
while(l+1<r){
int mid=(l+r)>>1;
f(j,0,p.size()) place[p[j]]=(j<mid);
if(ask(0,i)==0) l=mid;
else r=mid;
}
//cout<<endl<<i<<" : "<<endl;
//eror(p[l]);
//dbgv(p);
//dbgv(vec);
path(p[l],i,vec);
}
f(i,0,n){
//do_it(i);
}
}
/*
1
5 4
0 3
3 4
3 1
0 2
1
7 6
0 3
0 5
3 4
3 1
5 2
5 6
1 2
*/
Compilation message
park.cpp: In function 'void solve(int, int)':
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
89 | f(i,0,vec.size()) place[vec[i]]=(i<mid);
| ~~~~~~~~~~~~~~
park.cpp:89:3: note: in expansion of macro 'f'
89 | f(i,0,vec.size()) place[vec[i]]=(i<mid);
| ^
park.cpp: In function 'void Detect(int, int)':
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
133 | f(j,mid,A.size()) place[A[j]]=mark[A[j]];
| ~~~~~~~~~~~~~~
park.cpp:133:5: note: in expansion of macro 'f'
133 | f(j,mid,A.size()) place[A[j]]=mark[A[j]];
| ^
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
155 | f(j,0,p.size()) place[p[j]]=(j<mid);
| ~~~~~~~~~~~~
park.cpp:155:4: note: in expansion of macro 'f'
155 | f(j,0,p.size()) place[p[j]]=(j<mid);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Program terminated incorrectly, or you printed something to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
624 KB |
Program terminated incorrectly, or you printed something to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
380 ms |
480 KB |
Program terminated incorrectly, or you printed something to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
464 KB |
Program terminated incorrectly, or you printed something to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
732 KB |
Program terminated incorrectly, or you printed something to stdout |
| 2 |
Halted |
0 ms |
0 KB |
- |
