Submission #411677

#	Time	Username	Problem	Language	Result	Execution time	Memory
411677		Dormi	Through Another Maze Darkly (CCO21_day1problem3)	C++14	25 / 25	1963 ms	372076 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T>
int sz(const T &a){return int(a.size());}
const int MN=8e5+1;
vector<int> adj[MN];
vector<int> repord;
vector<vector<pii>> replaced;
int ind[MN];
int level[MN];
ll roomcnt[MN];
int etloc[MN],et;
vector<vector<vector<int>>> ord;
vector<ll> lroomcnt[MN];
vector<pii> locs[MN];
void dfspre(int loc, int parent, int cnt){
    level[loc]=cnt;
    ord[cnt].back().push_back(loc);
    int i=0;
    for(auto x:adj[loc]){
        if(x!=parent) {
            dfspre(x, loc,cnt);
            ord[cnt].back().push_back(loc);
        }
        else{
            ind[loc]=i;
            for(int j=i+1;j<sz(adj[loc]);j++){
                if(sz(ord)==cnt+1)ord.push_back({});
                ord[cnt+1].push_back({});
                dfspre(adj[loc][j],loc,cnt+1);
            }
            return;
        }
        i++;
    }
}
void dfs(int loc, int parent){
    repord.push_back(loc);
    etloc[loc]=et++;
    for(auto x:adj[loc]){
        if(x!=parent) {
            int st=-1,en=-1;
            if(level[x]!=level[loc]){
                st=sz(repord);
            }
            dfs(x, loc);
            if(level[x]!=level[loc]){
                en=sz(repord)-1;
            }
            if(st!=-1)replaced[level[x]].push_back({st,en});
            repord.push_back(loc);
        }
        else{
            return;
        }
    }
}
int main(int argc, char* argv[]){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,q;
    ll a;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a;
        adj[i].resize(a);
        for(int j=0;j<a;j++)cin>>adj[i][j];
        if(sz(adj[i])>=2)rotate(adj[i].begin(),adj[i].begin()+1,adj[i].end());
    }
    ord.push_back({});
    ord[0].push_back({});
    dfspre(1,0,0);
    ord[0][0].pop_back();
    for(int i=2;i<=n;i++){
        if(ind[i]+1!=sz(adj[i]))rotate(adj[i].begin(),adj[i].begin()+ind[i]+1,adj[i].end());
    }
    replaced.resize(sz(ord));
    et=1;
    dfs(1,0);
    repord.pop_back();
    roomcnt[0]=sz(ord[0][0]);
    for(int i=1;i<sz(ord);i++){
        sort(ord[i].begin(),ord[i].end(),[&](const vector<int> &lhs, const vector<int> &rhs){
            return etloc[lhs[0]]<etloc[rhs[0]];
        });
        assert(sz(replaced[i])==sz(ord[i]));
        ll tot=0;
        int leftoff=0;
        for(int j=0;j<sz(replaced[i]);j++){
            locs[i].push_back({leftoff,replaced[i][j].first-1});
            lroomcnt[i].push_back({replaced[i][j].first-leftoff+sz(ord[i][j])});
            leftoff=replaced[i][j].second+1;
            tot+=lroomcnt[i].back();
        }
        locs[i].push_back({leftoff,sz(repord)-1});
        lroomcnt[i].push_back({sz(repord)-leftoff});
        tot+=lroomcnt[i].back();
        for(int j=1;j<sz(lroomcnt[i]);j++){
            lroomcnt[i][j]+=lroomcnt[i][j-1];
        }
        roomcnt[i]=tot;
        roomcnt[i]+=roomcnt[i-1];
    }
    while(q--){
        cin>>a;
        a++;
        if(a>roomcnt[sz(ord)-1]){
            a-=roomcnt[sz(ord)-1];
            a-=1;
            a%=ll(sz(repord));
            printf("%d\n",repord[a]);
        }
        else{
            int wantedlevel=lower_bound(roomcnt,roomcnt+sz(ord),a)-roomcnt;
            if(wantedlevel==0){
                printf("%d\n",ord[0][0][a-1]);
            }
            else{
                a-=roomcnt[wantedlevel-1];
                int loc=lower_bound(lroomcnt[wantedlevel].begin(),lroomcnt[wantedlevel].end(),a)-lroomcnt[wantedlevel].begin();
                if(loc!=0)a-=lroomcnt[wantedlevel][loc-1];
                if(a<=locs[wantedlevel][loc].second-locs[wantedlevel][loc].first+1){
                    printf("%d\n",repord[locs[wantedlevel][loc].first+a-1]);
                }
                else{
                    printf("%d\n",ord[wantedlevel][loc][a-(locs[wantedlevel][loc].second-locs[wantedlevel][loc].first+1)-1]);
                }
            }
        }
    }
    return 0;
}

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