oj.uz

Submission #413345

# Submission time Handle Problem Language Result Execution time Memory
413345 2021-05-28T14:19:45 Z CodePlatina Through Another Maze Darkly (CCO21_day1problem3) C++17
16 / 25
 9000 ms 113580 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 = 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.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19276 KB Output is correct
2 Correct 1016 ms 20556 KB Output is correct
3 Execution timed out 9099 ms 31828 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19276 KB Output is correct
2 Correct 17 ms 19308 KB Output is correct
3 Correct 32 ms 19312 KB Output is correct
4 Correct 48 ms 19404 KB Output is correct
5 Correct 43 ms 19436 KB Output is correct
6 Correct 45 ms 19404 KB Output is correct
7 Correct 41 ms 19436 KB Output is correct
8 Correct 42 ms 19444 KB Output is correct
9 Correct 48 ms 19604 KB Output is correct
10 Correct 55 ms 19448 KB Output is correct
11 Correct 72 ms 19440 KB Output is correct
12 Correct 22 ms 19660 KB Output is correct
13 Correct 26 ms 19568 KB Output is correct
14 Correct 19 ms 19404 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19788 KB Output is correct
2 Correct 40 ms 22344 KB Output is correct
3 Correct 92 ms 26128 KB Output is correct
4 Correct 73 ms 24452 KB Output is correct
5 Correct 614 ms 70004 KB Output is correct
6 Correct 692 ms 69444 KB Output is correct
7 Correct 680 ms 57028 KB Output is correct
8 Correct 733 ms 69916 KB Output is correct
9 Correct 793 ms 85312 KB Output is correct
10 Correct 827 ms 81540 KB Output is correct
11 Correct 419 ms 113580 KB Output is correct
12 Correct 404 ms 100572 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19276 KB Output is correct
2 Correct 1016 ms 20556 KB Output is correct
3 Execution timed out 9099 ms 31828 KB Time limit exceeded
4 Halted 0 ms 0 KB -