oj.uz

답안 #413292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413292 2021-05-28T12:55:27 Z 최서현(#7481) Through Another Maze Darkly (CCO21_day1problem3) C++17
0 / 25
 32 ms 39676 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;

vector<int> gph[808080];
int par[808080];
vector<long long> dp[808080];

void dfs1(int x, int p)
{
    par[x] = -1;
    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 mx = 1;
    for(int i = 0; i < (int)gph[x].size(); ++i) if(i != par[x])
    {
        int y = gph[x][i];
        dfs2(y);
        mx = max(mx, (int)gph[y].size() + (i > par[x] ? 1 : 0));
    }

    dp[x].resize(mx);
    for(int i = 0; i < (int)gph[x].size(); ++i) if(i != par[x])
    {
        int y = gph[x][i];
        for(int j = 0; j < mx; ++j)
        {
            if(i < par[x])
            {
                if(j < (int)gph[y].size()) dp[x][j] += dp[y][j] + 2;
                else dp[x][j] += dp[y].back() + 2;
            }
            else
            {
                if(j == 0) ;
                else if(j < (int)gph[y].size()) dp[x][j] += dp[y][j - 1] + 2;
                else dp[x][j] += dp[y].back() + 2;
            }
        }
    }
}

int dfs3(int x, long long t, long long cnt)
{
    for(int i = 0; i < (int)gph[x].size(); ++i) if(i != par[x])
    {
        int y = gph[x][i];
        if(t == 0) return x;
        long long k;
        if(i < par[x]) k = t - (cnt < (int)dp[y].size() ? dp[y][cnt] + 2 : dp[y].back() + 2);
        else if(cnt == 0) break;
        else k = t - (cnt - 1 < (int)dp[y].size() ? dp[y][cnt - 1] + 2 : dp[y].back() + 2);
        if(k < 0) return dfs3(y, t - 1, cnt - (i > par[x] ? 1 : 0));
        else if(k == 0) return x;
        else t = k;
     }
    return x;
}

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);

    #ifdef DEBUG
        for(int i = 0; i < n; ++i)
        {
            cout << i << ": ";
            for(auto x : dp[i]) cout << x << ' ';
            cout << endl;
        }
    #endif // DEBUG

    while(T--)
    {
        long long t; cin >> t;
        int cnt = 0;
        while(cnt < (int)dp[0].size() && dp[0][cnt] <= t) t -= dp[0][cnt++];
        t %= dp[0].back();
        cout << dfs3(0, t, cnt) + 1 << '\n';
    }
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 38220 KB Output is correct
2 Incorrect 32 ms 39676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 38220 KB Output is correct
2 Incorrect 32 ms 39676 KB Output isn't correct
3 Halted 0 ms 0 KB -