oj.uz

답안 #411677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411677 2021-05-25T17:53:33 Z Dormi Through Another Maze Darkly (CCO21_day1problem3) C++14
25 / 25
 1963 ms 372076 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 50 ms 59604 KB Output is correct
3 Correct 171 ms 85728 KB Output is correct
4 Correct 760 ms 209788 KB Output is correct
5 Correct 1650 ms 372076 KB Output is correct
6 Correct 1375 ms 289872 KB Output is correct
7 Correct 376 ms 88276 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 56588 KB Output is correct
2 Correct 36 ms 56748 KB Output is correct
3 Correct 36 ms 56864 KB Output is correct
4 Correct 36 ms 56836 KB Output is correct
5 Correct 36 ms 56932 KB Output is correct
6 Correct 37 ms 56900 KB Output is correct
7 Correct 51 ms 56936 KB Output is correct
8 Correct 40 ms 56920 KB Output is correct
9 Correct 38 ms 57052 KB Output is correct
10 Correct 36 ms 57072 KB Output is correct
11 Correct 36 ms 57028 KB Output is correct
12 Correct 36 ms 57408 KB Output is correct
13 Correct 36 ms 57288 KB Output is correct
14 Correct 39 ms 57032 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 58316 KB Output is correct
2 Correct 75 ms 65104 KB Output is correct
3 Correct 132 ms 75804 KB Output is correct
4 Correct 124 ms 68032 KB Output is correct
5 Correct 979 ms 133236 KB Output is correct
6 Correct 1022 ms 132924 KB Output is correct
7 Correct 942 ms 138452 KB Output is correct
8 Correct 1016 ms 152968 KB Output is correct
9 Correct 1151 ms 203768 KB Output is correct
10 Correct 1186 ms 228620 KB Output is correct
11 Correct 873 ms 366628 KB Output is correct
12 Correct 703 ms 284436 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 50 ms 59604 KB Output is correct
3 Correct 171 ms 85728 KB Output is correct
4 Correct 760 ms 209788 KB Output is correct
5 Correct 1650 ms 372076 KB Output is correct
6 Correct 1375 ms 289872 KB Output is correct
7 Correct 376 ms 88276 KB Output is correct
8 Correct 34 ms 56588 KB Output is correct
9 Correct 36 ms 56748 KB Output is correct
10 Correct 36 ms 56864 KB Output is correct
11 Correct 36 ms 56836 KB Output is correct
12 Correct 36 ms 56932 KB Output is correct
13 Correct 37 ms 56900 KB Output is correct
14 Correct 51 ms 56936 KB Output is correct
15 Correct 40 ms 56920 KB Output is correct
16 Correct 38 ms 57052 KB Output is correct
17 Correct 36 ms 57072 KB Output is correct
18 Correct 36 ms 57028 KB Output is correct
19 Correct 36 ms 57408 KB Output is correct
20 Correct 36 ms 57288 KB Output is correct
21 Correct 39 ms 57032 KB Output is correct
22 Correct 40 ms 58316 KB Output is correct
23 Correct 75 ms 65104 KB Output is correct
24 Correct 132 ms 75804 KB Output is correct
25 Correct 124 ms 68032 KB Output is correct
26 Correct 979 ms 133236 KB Output is correct
27 Correct 1022 ms 132924 KB Output is correct
28 Correct 942 ms 138452 KB Output is correct
29 Correct 1016 ms 152968 KB Output is correct
30 Correct 1151 ms 203768 KB Output is correct
31 Correct 1186 ms 228620 KB Output is correct
32 Correct 873 ms 366628 KB Output is correct
33 Correct 703 ms 284436 KB Output is correct
34 Correct 308 ms 62256 KB Output is correct
35 Correct 365 ms 70792 KB Output is correct
36 Correct 572 ms 82068 KB Output is correct
37 Correct 1356 ms 138972 KB Output is correct
38 Correct 1524 ms 138276 KB Output is correct
39 Correct 1351 ms 143796 KB Output is correct
40 Correct 1499 ms 155296 KB Output is correct
41 Correct 1754 ms 214288 KB Output is correct
42 Correct 1963 ms 289896 KB Output is correct
43 Correct 1479 ms 371688 KB Output is correct
44 Correct 1294 ms 289712 KB Output is correct
45 Correct 1482 ms 222332 KB Output is correct
46 Correct 36 ms 56604 KB Output is correct