oj.uz

Submission #696407

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 19 ms 22228 KB Output is correct
3 Correct 120 ms 49344 KB Output is correct
4 Correct 785 ms 242936 KB Output is correct
5 Correct 1153 ms 274152 KB Output is correct
6 Correct 1157 ms 262008 KB Output is correct
7 Correct 307 ms 62496 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19176 KB Output is correct
2 Correct 11 ms 19168 KB Output is correct
3 Correct 12 ms 19312 KB Output is correct
4 Correct 12 ms 19444 KB Output is correct
5 Correct 11 ms 19412 KB Output is correct
6 Correct 12 ms 19436 KB Output is correct
7 Incorrect 12 ms 19412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 19 ms 22228 KB Output is correct
3 Correct 120 ms 49344 KB Output is correct
4 Correct 785 ms 242936 KB Output is correct
5 Correct 1153 ms 274152 KB Output is correct
6 Correct 1157 ms 262008 KB Output is correct
7 Correct 307 ms 62496 KB Output is correct
8 Correct 13 ms 19176 KB Output is correct
9 Correct 11 ms 19168 KB Output is correct
10 Correct 12 ms 19312 KB Output is correct
11 Correct 12 ms 19444 KB Output is correct
12 Correct 11 ms 19412 KB Output is correct
13 Correct 12 ms 19436 KB Output is correct
14 Incorrect 12 ms 19412 KB Output isn't correct
15 Halted 0 ms 0 KB -