oj.uz

Submission #112844

# Submission time Handle Problem Language Result Execution time Memory
112844 2019-05-22T06:52:46 Z ckodser Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 17524 KB 
#include<bits/stdc++.h>
#include<Joi.h>


#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e9+900;

vector<ll> ger[maxn];
vector<ll> tree[maxn];

bool vis[maxn];
bool ans[maxn];
bool in_path[maxn];
ll h[maxn];
ll chand[maxn];
vector<ll> tartib;
vector<ll> dfss;
ll newras;

void clearr(){
    memset(ans,0,sizeof ans);
    memset(h,0,sizeof h);
    memset(in_path,0,sizeof in_path);
    memset(chand,0,sizeof chand);

    tartib.clear();
    dfss.clear();
    for(ll i=0;i<maxn;i++){
	ger[i].clear();
	tree[i].clear();
    }
}
pii find_far(ll v){
    vis[v]=1;
    pii ans=mp(0,v);
    for(auto u:ger[v]){
	if(!vis[u]){
	    pii e=find_far(u);
	    e.F++;
	    ans=max(ans,e);
	}
    }
    return ans;
}
pair<pii,ll> find_rot(ll n,ll m){
    pii e=find_far(0);
    memset(vis,0,sizeof vis);
    pii r=find_far(e.S);
    memset(vis,0,sizeof vis);
    return mp(mp(r.S,e.S),r.F); 
}
bool  dfs(ll a,ll b){
    bool ans=0;
    if(a==b)ans=1;
    vis[a]=1;
    for(auto v:ger[a]){
	if(!vis[v]){
	    tree[a].pb(v);
	    ans|=dfs(v,b);
	}
    }
    in_path[a]=ans;
    return ans;
}
void dfs_2(ll a){
    tartib.pb(a);
    dfss.pb(a);
    if(!in_path[a])newras--;
    for(auto v:tree[a]){
	if(newras && in_path[v]==0){
	    dfs_2(v);
	    dfss.pb(a);
	}
    }
    for(auto v:tree[a]){
	if(in_path[v]){
	    dfs_2(v);
	}
    }
}
void make_tartib(pair<pii,ll> e){
    ll a=e.F.F;
    ll b=e.F.S;
    memset(vis,0,sizeof vis);
    dfs(a,b);
    newras=60-(e.S+1);
    dfs_2(a);
}
void bfs(ll a){
    memset(vis,0,sizeof vis);
    memset(h,0,sizeof h);
    queue<ll> qu;
    qu.push(a);
    vis[a]=1;
    h[a]=0;
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(!vis[u]){
		qu.push(u);
		vis[u]=1;
		h[u]=h[v]+1;
	    }
	}
    }
}
void Joi(int n, int m, int A[], int B[], long long X, int T){
    clearr();    
    for(ll i=0;i<m;i++){
	ger[A[i]].pb(B[i]);
	ger[B[i]].pb(A[i]);
    }
    pair<pii,ll> ew=find_rot(n,m);
    pii r=mp(ew.S,ew.F.F);
    if(r.F>=60){
	bfs(r.S);
	for(ll i=0;i<n;i++){
	    ans[i]=((X>>(h[i]%60))&1);
	    MessageBoard(i,ans[i]);
	}
	return ;
    }else{
	make_tartib(ew);
	set<ll> st;
	for(ll i=0;i<n;i++){
	    st.insert(i);
	}
	for(ll i=0;i<(ll)tartib.size();i++){
	    MessageBoard(tartib[i],(X>>i)&1);
	    st.erase(tartib[i]);
	}
	for(auto v:st){
	    MessageBoard(v,0);
	}
	return;
    }
}

#include<bits/stdc++.h>
#include<Ioi.h>


#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e9+900;


vector<ll> ger[maxn];
vector<ll> tree[maxn];

bool vis[maxn];
bool ans[maxn];
bool in_path[maxn];
ll h[maxn];
vector<ll> tartib;
vector<ll> dfss;
ll chand[maxn];
ll newras;

void clearr(){
    memset(ans,0,sizeof ans);
    memset(h,0,sizeof h);
    memset(in_path,0,sizeof in_path);
    memset(chand,0,sizeof chand);
    tartib.clear();
    dfss.clear();
    for(ll i=0;i<maxn;i++){
	ger[i].clear();
	tree[i].clear();
    }
}
pii find_far(ll v){
    vis[v]=1;
    pii ans=mp(0,v);
    for(auto u:ger[v]){
	if(!vis[u]){
	    pii e=find_far(u);
	    e.F++;
	    ans=max(ans,e);
	}
    }
    return ans;
}
pair<pii,ll> find_rot(ll n,ll m){
    pii e=find_far(0);
    memset(vis,0,sizeof vis);
    pii r=find_far(e.S);
    memset(vis,0,sizeof vis);
    return mp(mp(r.S,e.S),r.F); 
}
bool  dfs(ll a,ll b){
    bool ans=0;
    if(a==b)ans=1;
    vis[a]=1;
    for(auto v:ger[a]){
	if(!vis[v]){
	    tree[a].pb(v);
	    ans|=dfs(v,b);
	}
    }
    in_path[a]=ans;
    return ans;
}
void dfs_2(ll a){
    tartib.pb(a);
    dfss.pb(a);
    if(!in_path[a])newras--;
    for(auto v:tree[a]){
	if(newras && in_path[v]==0){
	    dfs_2(v);
	    dfss.pb(a);
	}
    }
    for(auto v:tree[a]){
	if(in_path[v]){
	    dfs_2(v);
	}
    }
}
void make_tartib(pair<pii,ll> e){
    ll a=e.F.F;
    ll b=e.F.S;
    memset(vis,0,sizeof vis);
    dfs(a,b);
    newras=60-(e.S+1);
    dfs_2(a);
}
void bfs(ll a){
    memset(vis,0,sizeof vis);
    memset(h,0,sizeof h);
    queue<ll> qu;
    qu.push(a);
    vis[a]=1;
    h[a]=0;
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(!vis[u]){
		qu.push(u);
		vis[u]=1;
		h[u]=h[v]+1;
	    }
	}
    }
}

long long Ioi(int n, int m, int A[], int B[],int p,int v, int T){
    clearr();    
    for(ll i=0;i<m;i++){
	ger[A[i]].pb(B[i]);
	ger[B[i]].pb(A[i]);
    }
    pair<pii,ll> ew=find_rot(n,m);
    pii r=mp(ew.S,ew.F.F);
    bfs(r.F);
    if(r.F>=60){
	while(h[p]%60!=0){
	    for(auto u:ger[p]){
		if(h[u]==h[p]-1){
		    v=move(u);
		    p=u;
		    break;
		}
	    }
	}
	if(h[p]==0){
	    while(h[p]%60!=59){
		ans[h[p]%60]=v;
		for(auto u:ger[p]){
		    if(h[u]==h[p]+1){
			v=move(u);
			p=u;
			break;
		    }
		}
	    }
	    ans[h[p]%60]=v;
	}else{
    	    for(ll i=0;i<60;i++){
		ans[h[p]%60]=v;
		for(auto u:ger[p]){
		    if(h[u]==h[p]-1){
			v=move(u);
			p=u;
			break;
		    }
		}
	    }
	    ans[h[p]%60]=v;
	}
	ll x=0;
	for(ll i=0;i<60;i++){
	    x+=(1LL<<i)*ans[i];
	}
	return x;
    }else{
	make_tartib(ew);
	while(h[p]!=0){
	    for(auto u:ger[p]){
		if(h[u]==h[p]-1){
		    v=move(u);
		    p=u;
		    break;
		}
	    }
	}
	for(ll i=0;i<(ll)tartib.size();i++){
	    chand[tartib[i]]=i+1;
	}
	if(chand[p]){
	    ans[chand[p]-1]=v;
	}
	for(ll i=1;i<(ll)dfss.size();i++){
	    v=move(dfss[i]);
	    p=dfss[i];
	    if(chand[p]){
		ans[chand[p]-1]=v;
	    }
	}
	ll x=0;
	for(ll i=0;i<60;i++){
	    x+=(1LL<<i)*ans[i];
	}
	return x;

    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 13984 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 17524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 13824 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 17492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 17500 KB Time limit exceeded
2 Halted 0 ms 0 KB -