oj.uz

Submission #413331

# Submission time Handle Problem Language Result Execution time Memory
413331 2021-05-28T13:48:51 Z 최서현(#7481) Through Another Maze Darkly (CCO21_day1problem3) C++17
0 / 25
 9000 ms 31840 KB 
#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 = 0; i < (int)gph[x].size(); ++i) if(i != par[x] && 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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19276 KB Output is correct
2 Correct 823 ms 20556 KB Output is correct
3 Execution timed out 9021 ms 31840 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19788 KB Output is correct
2 Incorrect 38 ms 22368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19276 KB Output is correct
2 Correct 823 ms 20556 KB Output is correct
3 Execution timed out 9021 ms 31840 KB Time limit exceeded
4 Halted 0 ms 0 KB -