oj.uz

Submission #120548

# Submission time Handle Problem Language Result Execution time Memory
120548 2019-06-24T20:33:13 Z shayan_p Park (JOI17_park) C++14
100 / 100
 360 ms 796 KB 
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include "park.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1600;

vector<int> v[maxn], start ,vec ,vec2;
bool bad[maxn], mark[maxn], done[maxn];
int n, arr[maxn], Cnt;

/*

void Answer(int a,int b){
    cout<<"Found "<<a<<" "<<b<<endl;
}

bool mark2[maxn];
vector<int>v2[maxn];

void dfs2(int u,int *arr){
    mark2[u]=1;
    for(int y:v2[u]){
	if(mark2[y]==0 && arr[y])
	    dfs2(y,arr);
    }
}
int Ask(int a,int b,int *arr){
    assert( arr[a] && arr[b] );
    memset(mark2,0,sizeof mark2);
    dfs2(a,arr);
    return mark2[b];
}
*/
void _Answer(int a,int b){
    if(a>b) swap(a,b);
    return Answer(a,b);
}
int _Ask(int a,int b,int *arr){
    assert(a!=b && arr[a] && arr[b]);
    if(a>b) swap(a,b);
    return Ask(a,b,arr);		
}

void Dfs(int u){
    mark[u]=1;
    start.PB(u);
    for(int y:v[u]){
	if(mark[y]==0 && bad[y]==0)
	    Dfs(y);
    }
}
int Bs(int u){
    int l=-1,r=sz(start)-1;
    while(r-l > 1){
	int mid=(l+r)>>1;

	for(int i=0;i<n;i++)
	    arr[i]=0;
	for(int i=0;i<=mid;i++)
	    arr[ start[i] ]=1;
	arr[u]=1;
	
	if(_Ask(u,start[0],arr)) r=mid;
	else l=mid;
    }
    return start[r];
}
void Push(int u,int r){
    memset(mark,0,sizeof mark);
    start.clear(), Dfs(r);

    for(int i=0;i<n;i++)
	arr[i]=mark[i];
    arr[u]=arr[r]=1;
    if(_Ask(u,r,arr)==0) return;
    
    int w= Bs(u);
    _Answer(u,w), v[u].PB(w), v[w].PB(u), bad[w]=1;

    memset(mark,0,sizeof mark);
    
    vector<int>vec;
    
    for(int y:v[w]){
	if(mark[y]==0 && !bad[y]) vec.PB(y), Dfs(y);
    }
    for(int y:vec){
	Push(u,y);
    }
}
void Path(int u,int l=0,int r=sz(vec2)){
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=0;
    }
    if(_Ask(0,u,arr)) return;
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=1;
    }
    if(r-l==1) { vec.PB(vec2[l]); return; }
    int mid=(l+r)>>1;
    Path(u,l,mid), Path(u,mid,r);
}

void Detect(int _,int n){
    srand(time(0));
    ::n=n;
    
    done[0]=1, Cnt=1;
    
    while(Cnt<n){
	int id=rand()%(n-Cnt);
	
	for(int i=0;i<n;i++){
	    if(done[i]) continue;
	    if(id==0){ id=i; break; }
	    id--;
	}
	
	memset(arr,0,sizeof arr);
	vec.clear(), vec2.clear();
	for(int i=0;i<n;i++){
	    arr[i]=1;
	    if(i!=id && !done[i]) vec2.PB(i);
	}
	vec.PB(id), Path(id);

	for(int i=0;i<n;i++){
	    arr[i]=0;
	}
	for(int x:vec){
	    arr[x]=1;
	}

	auto cmp=[&](int a,int b){
	    if(a==b) return false;
	    if(a==id) return false;
	    if(b==id) return true;
	    
	    arr[a]=0;
	    bool ans=_Ask(b,id,arr);
	    arr[a]=1;
	    return ans;
	};

	sort(vec.begin(), vec.end(), cmp);
	
	for(int x:vec){    
	    memset(bad,0,sizeof bad);
	    bad[x]=1;
	    Push(x,0);
	    done[x]=1;
	    Cnt++;
	}
    }
}
/*
int main(){
    int n,m; cin>>n>>m;
    while(m--){
	int a,b; cin>>a>>b;
	v2[a].PB(b), v2[b].PB(a);
    }
    Detect(-1,n);
    return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 18 ms 512 KB Output is correct
5 Correct 35 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 588 KB Output is correct
2 Correct 194 ms 668 KB Output is correct
3 Correct 184 ms 632 KB Output is correct
4 Correct 252 ms 796 KB Output is correct
5 Correct 250 ms 760 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 512 KB Output is correct
2 Correct 227 ms 512 KB Output is correct
3 Correct 242 ms 632 KB Output is correct
4 Correct 212 ms 512 KB Output is correct
5 Correct 252 ms 636 KB Output is correct
6 Correct 225 ms 632 KB Output is correct
7 Correct 213 ms 584 KB Output is correct
8 Correct 232 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 524 KB Output is correct
2 Correct 256 ms 580 KB Output is correct
3 Correct 274 ms 512 KB Output is correct
4 Correct 235 ms 632 KB Output is correct
5 Correct 249 ms 636 KB Output is correct
6 Correct 219 ms 636 KB Output is correct
7 Correct 196 ms 632 KB Output is correct
8 Correct 235 ms 512 KB Output is correct
9 Correct 234 ms 512 KB Output is correct
10 Correct 242 ms 632 KB Output is correct
11 Correct 245 ms 512 KB Output is correct
12 Correct 249 ms 512 KB Output is correct
13 Correct 222 ms 512 KB Output is correct
14 Correct 251 ms 632 KB Output is correct
15 Correct 227 ms 584 KB Output is correct
16 Correct 238 ms 512 KB Output is correct
17 Correct 260 ms 632 KB Output is correct
18 Correct 360 ms 772 KB Output is correct
19 Correct 238 ms 572 KB Output is correct
20 Correct 236 ms 628 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 632 KB Output is correct
2 Correct 325 ms 632 KB Output is correct
3 Correct 263 ms 512 KB Output is correct
4 Correct 248 ms 632 KB Output is correct
5 Correct 331 ms 632 KB Output is correct
6 Correct 269 ms 664 KB Output is correct
7 Correct 282 ms 636 KB Output is correct
8 Correct 251 ms 632 KB Output is correct
9 Correct 254 ms 644 KB Output is correct
10 Correct 273 ms 632 KB Output is correct
11 Correct 224 ms 632 KB Output is correct
12 Correct 278 ms 568 KB Output is correct
13 Correct 253 ms 632 KB Output is correct
14 Correct 331 ms 760 KB Output is correct
15 Correct 234 ms 660 KB Output is correct
16 Correct 238 ms 512 KB Output is correct
17 Correct 274 ms 732 KB Output is correct
18 Correct 209 ms 632 KB Output is correct