oj.uz

Submission #696405

# Submission time Handle Problem Language Result Execution time Memory
696405 2023-02-06T12:26:07 Z benedict0724 Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 1042 ms 274232 KB 
#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=0;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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 18 ms 22288 KB Output is correct
3 Correct 122 ms 49412 KB Output is correct
4 Correct 754 ms 242928 KB Output is correct
5 Correct 1034 ms 274232 KB Output is correct
6 Correct 1042 ms 262252 KB Output is correct
7 Correct 292 ms 62456 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 13 ms 19268 KB Output is correct
3 Correct 10 ms 19284 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 12 ms 19412 KB Output is correct
6 Correct 12 ms 19420 KB Output is correct
7 Incorrect 12 ms 19460 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 20556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 18 ms 22288 KB Output is correct
3 Correct 122 ms 49412 KB Output is correct
4 Correct 754 ms 242928 KB Output is correct
5 Correct 1034 ms 274232 KB Output is correct
6 Correct 1042 ms 262252 KB Output is correct
7 Correct 292 ms 62456 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 13 ms 19268 KB Output is correct
10 Correct 10 ms 19284 KB Output is correct
11 Correct 14 ms 19412 KB Output is correct
12 Correct 12 ms 19412 KB Output is correct
13 Correct 12 ms 19420 KB Output is correct
14 Incorrect 12 ms 19460 KB Output isn't correct
15 Halted 0 ms 0 KB -