Submission #696407

#	Time	Username	Problem	Language	Result	Execution time	Memory
696407		benedict0724	Through Another Maze Darkly (CCO21_day1problem3)	C++17	4 / 25	1157 ms	274152 KiB

Main

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

#define int ll

using namespace std;
typedef long long ll;

vector<int> adj[800002];
vector<vector<int>> levNode;
vector<pair<int, int>> path;

vector<pair<ll, int>> ask;
int ans[800002];

int T[6400000];
void upd(int i, int l, int r, int id)
{
    if(l == r)
    {
        T[i]++;
        return;
    }
    int m = (l + r)/2;
    if(id <= m) upd(i*2, l, m, id);
    else upd(i*2+1, m+1, r, id);
    
    T[i] = T[i*2] + T[i*2+1];
}

int f(int i, int l, int r, int id)
{
    if(l == r) return path[l].first;
    int m = (l + r)/2;
    if(T[i*2] < id) return f(i*2+1, m+1, r, id-T[i*2]);
    else return f(i*2, l, m, id);
}

int maxLev = 0;

void dfs(int x, int p, int lev)
{
    maxLev = max(maxLev, lev);
    if(x != 1) path.push_back({x, lev});
    int sz = (int)adj[x].size();
    int loc = 0;
    
    if(x == 1)
    {
        for(int i=1;i<sz;i++)
        {
            dfs(adj[x][i], x, lev);
            path.push_back({x, lev});
        }
        dfs(adj[x][0], x, lev);
        path.push_back({x, lev});
    }
    for(int i=0;i<sz;i++)
    {
        if(adj[x][i] == p)
        {
            loc = i;
            break;
        }
    }
    if(loc == 0)
    {
        for(int i=1;i<sz;i++) {
            dfs(adj[x][i], x, lev);
            path.push_back({x, lev});
        }
    }
    else
    {
        for(int i=loc+1;i<sz;i++) {
            dfs(adj[x][i], x, lev+1);
            path.push_back({x, lev+1});
        }
        dfs(adj[x][0], x, lev+1);
        path.push_back({x, lev+1});
        for(int i=1;i<loc;i++) {
            dfs(adj[x][i], x, lev);
            path.push_back({x, lev});
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        int c; cin >> c;
        for(int j=1;j<=c;j++)
        {
            int v; cin >> v;
            adj[i].push_back(v);
        }
    }
    
    dfs(1, -1, 0);
    int L = (int)path.size();
    levNode.resize(maxLev+1);
    for(int i=0;i<L;i++)
    {
        //cout << path[i].first << " " << path[i].second << "\n";
        levNode[path[i].second].push_back(i);
    }
    
    for(int i=1;i<=q;i++)
    {
        ll asdf; cin >> asdf;
        ask.push_back({asdf, i});
    }
    sort(ask.begin(), ask.end());
    
    ll now = 0, num = 0, nL = 0;
    for(int i=0;i<q;i++)
    {
        while(now < ask[i].first && nL <= maxLev)
        {
            num += levNode[nL].size();
            now += num;
            
            for(int j : levNode[nL]){
                upd(1, 0, L-1, j);
            }
            
            nL++;
        }
        
        if(nL <= maxLev)
        {
            ll x = ask[i].first - now + num;
            ans[ask[i].second] = f(1, 0, L-1, x);
        }
        else
        {
            ll x = (ask[i].first - now + L)%L;
            if(x == 0) x = L;
            ans[ask[i].second] = f(1, 0, L-1, x);
        }
    }

    for(int i=1;i<=q;i++)
    {
        cout << ans[i] << "\n";
    }
}

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