oj.uz

Submission #696406

# Submission time Handle Problem Language Result Execution time Memory
696406 2023-02-06T12:26:33 Z benedict0724 Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 1062 ms 274172 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 10 ms 19028 KB Output is correct
2 Correct 20 ms 22232 KB Output is correct
3 Correct 116 ms 49368 KB Output is correct
4 Correct 771 ms 243000 KB Output is correct
5 Correct 1062 ms 274172 KB Output is correct
6 Correct 1036 ms 262108 KB Output is correct
7 Correct 286 ms 62392 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19164 KB Output is correct
2 Correct 12 ms 19256 KB Output is correct
3 Correct 11 ms 19380 KB Output is correct
4 Correct 11 ms 19412 KB Output is correct
5 Correct 14 ms 19436 KB Output is correct
6 Correct 12 ms 19372 KB Output is correct
7 Incorrect 11 ms 19384 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 10 ms 19028 KB Output is correct
2 Correct 20 ms 22232 KB Output is correct
3 Correct 116 ms 49368 KB Output is correct
4 Correct 771 ms 243000 KB Output is correct
5 Correct 1062 ms 274172 KB Output is correct
6 Correct 1036 ms 262108 KB Output is correct
7 Correct 286 ms 62392 KB Output is correct
8 Correct 11 ms 19164 KB Output is correct
9 Correct 12 ms 19256 KB Output is correct
10 Correct 11 ms 19380 KB Output is correct
11 Correct 11 ms 19412 KB Output is correct
12 Correct 14 ms 19436 KB Output is correct
13 Correct 12 ms 19372 KB Output is correct
14 Incorrect 11 ms 19384 KB Output isn't correct
15 Halted 0 ms 0 KB -