oj.uz

답안 #696399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696399 2023-02-06T11:52:30 Z benedict0724 Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 1030 ms 274184 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+1);
        path.push_back({x, lev+1});
    }
    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);
    //freopen("/Users/chaeihwan/Downloads/day1data/cco_d1p3/d1p3.3-22.in", "r", stdin);
    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);
        }
    }
    
    //freopen("/Users/chaeihwan/Downloads/day1data/cco_d1p3/d1p3.3-22.out", "r", stdin);
    for(int i=1;i<=q;i++)
    {
        //int expect; cin >> expect;
        //if(ans[i] != expect) cout << "i = " << i << ", " << "out = " << ans[i] << ", expected = " << expect << "\n";
        cout << ans[i] << "\n";
    }
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 19 ms 22320 KB Output is correct
3 Correct 122 ms 49372 KB Output is correct
4 Correct 768 ms 242864 KB Output is correct
5 Correct 1008 ms 274184 KB Output is correct
6 Correct 1030 ms 262124 KB Output is correct
7 Correct 288 ms 62444 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19156 KB Output is correct
3 Correct 12 ms 19384 KB Output is correct
4 Correct 11 ms 19436 KB Output is correct
5 Correct 13 ms 19388 KB Output is correct
6 Correct 13 ms 19448 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 20556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 19 ms 22320 KB Output is correct
3 Correct 122 ms 49372 KB Output is correct
4 Correct 768 ms 242864 KB Output is correct
5 Correct 1008 ms 274184 KB Output is correct
6 Correct 1030 ms 262124 KB Output is correct
7 Correct 288 ms 62444 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 10 ms 19156 KB Output is correct
10 Correct 12 ms 19384 KB Output is correct
11 Correct 11 ms 19436 KB Output is correct
12 Correct 13 ms 19388 KB Output is correct
13 Correct 13 ms 19448 KB Output is correct
14 Incorrect 12 ms 19412 KB Output isn't correct
15 Halted 0 ms 0 KB -