Submission #1207110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207110		boclobanchat	Through Another Maze Darkly (CCO21_day1problem3)	C++20	4 / 25	824 ms	806068 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8e5+5;
deque<int> nex[MAXN];
vector<int> ds[MAXN],vi[MAXN],vd[MAXN],vq[MAXN],sd[MAXN];
int root[MAXN],fen[MAXN*2],pos[MAXN],L[MAXN],R[MAXN],tdfs=0;
bool ck[MAXN],ft[MAXN];
long long F[MAXN],Q[MAXN],ans[MAXN];
void predfs(int i,int pre)
{
	root[i]=pre;
	for(auto v:ds[i]) if(v!=pre) predfs(v,i);
}
void dfs(int i,int pre)
{
	L[i]=++tdfs,pos[tdfs]=i;
	for(auto v:sd[i]) dfs(v,i);
	R[i]=++tdfs,pos[tdfs]=pre;
}
void dfsus(int i,int idx)
{
	if(!ft[i])
	{
		ft[i]=true;
		vi[idx].push_back(L[i]);
	}
	while(!nex[i].empty())
	{
		int v=nex[i].front();
		nex[i].pop_front();
		if(v==root[i])
		{
			if(!nex[i].empty()) vd[idx].push_back(i);
			break;
		}
		dfsus(v,idx);
		if(R[v]!=tdfs-1) vi[idx].push_back(R[v]);
	}
}
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
    	int k;
    	cin>>k;
    	while(k--)
    	{
    		int res;
    		cin>>res;
    		nex[i].push_back(res);
		}
		nex[i].push_back(nex[i].front()),nex[i].pop_front();
		deque<int> res=nex[i];
		while(!res.empty())
		{
			int v=res.front();
			ds[i].push_back(v),res.pop_front();
		}
	}
	predfs(1,1);
	for(int i=1;i<=n;i++) if(i==1) sd[i]=ds[i];
	else
	{
		int sz=ds[i].size();
		for(int j=0;j<sz;j++) if(ds[i][j]==root[i])
		{
			for(int k=j+1;k<sz;k++) sd[i].push_back(ds[i][k]);
			for(int k=0;k<j;k++) sd[i].push_back(ds[i][k]);
		}
	}
	dfs(1,1);
	vi[0].push_back(1),vd[0].push_back(1);
	int idx=0;
	while(true)
	{
		if(vd[idx].empty()) break;
		for(auto v:vd[idx]) dfsus(v,idx+1);
		idx++,F[idx]=vi[idx].size()+F[idx-1];
	}
	for(int i=1;i<=idx;i++) F[i]+=F[i-1];
	F[++idx]=1e18;
	for(int i=1;i<=q;i++)
	{
		long long res;
		cin>>res;
		res++;
		int pos=lower_bound(F+1,F+idx+1,res)-F;
		vq[pos].push_back(i),Q[i]=res;
	}
	for(int i=1;i<=idx;i++)
	{
		for(auto v:vi[i]) update(v,tdfs,1);
		if(i<idx)
		{
			for(auto v:vq[i])
			{
				long long k=Q[v];
				ans[v]=pos[walk(tdfs,k-F[i-1])];
			}
		}
		else
		{
			for(auto v:vq[i])
			{
				long long k=Q[v];
				ans[v]=pos[(k-F[i-1]+tdfs-3)%(tdfs-2)+1];
			}
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5