Submission #413345

#	Time	Username	Problem	Language	Result	Execution time	Memory
413345		CodePlatina	Through Another Maze Darkly (CCO21_day1problem3)	C++17	16 / 25	9099 ms	113580 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <deque>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

const int INF = (int)1e9 + 7;
vector<int> gph[808080];
int par[808080];
int dp[808080];

void dfs1(int x, int p)
{
    par[x] = INF;
    for(int i = 0; i < (int)gph[x].size(); ++i)
    {
        if(gph[x][i] == p) par[x] = i;
        else dfs1(gph[x][i], x);
    }
}

void dfs2(int x, int d)
{
    dp[x] = d;
    for(int i = 0; i < (int)gph[x].size(); ++i) if(i != par[x])
    {
        if(i < par[x]) dfs2(gph[x][i], d);
        else dfs2(gph[x][i], d + 1);
    }
}

int dfs3(int x, long long &t, int cnt)
{
    if(t == 0) return x;
    for(int i = par[x] + 1; i < (int)gph[x].size(); ++i) if(dp[gph[x][i]] <= cnt)
    {
        --t;
        int ret = dfs3(gph[x][i], t, cnt);
        if(ret != -1) return ret;
        if(t == 0) return x;
    }
    for(int i = 0; i < par[x]; ++i) if(dp[gph[x][i]] <= cnt)
    {
        --t;
        int ret = dfs3(gph[x][i], t, cnt);
        if(ret != -1) return ret;
        if(t == 0) return x;
    }

    --t;
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T; cin >> n >> T;
    for(int i = 0; i < n; ++i)
    {
        int t; cin >> t;
        int x; cin >> x; --x;
        for(int j = 1; j < t; ++j)
        {
            int y; cin >> y; --y;
            gph[i].push_back(y);
        }
        gph[i].push_back(x);
    }

    dfs1(0, -1);
    dfs2(0, 0);

    long long len[n]{};
    for(int i = 0; i < n; ++i) ++len[dp[i]];
    for(int i = 1; i < n; ++i) len[i] += len[i - 1];
    for(int i = 0; i < n; ++i) len[i] = 2 * len[i] - 2;
    for(int i = 1; i < n; ++i) len[i] += len[i - 1];

    while(T--)
    {
        long long t; cin >> t;
        int k = lower_bound(len, len + n, t) - len;
        if(k == n)
        {
            t -= len[n - 1];
            t %= (2 * n - 2);
            cout << dfs3(0, t, k) + 1 << '\n';
        }
        else
        {
            if(k) t -= len[k - 1];
            cout << dfs3(0, t, k) + 1 << '\n';
        }
    }
}

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