oj.uz

답안 #478803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478803 2021-10-08T12:15:56 Z blue Through Another Maze Darkly (CCO21_day1problem3) C++17
25 / 25
 7849 ms 864880 KB 
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

const int maxN = 800'000;
const int maxQ = 800'000;

deque<int> edge[1+maxN];
vector<int> parent(1+maxN, 0);
vector<int> init_arrow(1+maxN);

vector<int> euler;
vector<int> first_dfs;
vector<bool> visit(1+maxN, 0);

void dfs1(int u)
{
    for(int v: edge[u])
    {
        if(visit[v]) continue;
        visit[v] = 1;

        parent[v] = u;
        // cerr << "parent " << v << " = " << parent[v] << '\n';
        dfs1(v);
    }
}


void dfs2(int u)
{
    // cerr << "first dfs " << u << ' ' << e << '\n';
    for(int v: edge[u])
    {
        // cerr << u << " -> " << v << '\n';
        // cerr << (v == )
        // if(v == init_arrow[u]) new_dfs = 0;
        if(v == parent[u]) continue;

        euler.push_back(v);
        dfs2(v);
        euler.push_back(u);
    }
}


int euler_ct = -1;
void dfs3(int u, int e)
{
    int new_dfs = 1;
    for(int v: edge[u])
    {
        if(v == init_arrow[u]) new_dfs = 0;
        if(v == parent[u]) continue;

        first_dfs.push_back(e + new_dfs);
        dfs3(v, e + new_dfs);
        first_dfs.push_back(e + new_dfs);
    }
}




struct query
{
    long long K;
    int i;
};

bool operator < (query A, query B)
{
    return A.K < B.K;
}

vector<int> answer(maxQ, -1);



struct segtree //add +1, count the number of +1s in a given region.
{
    int l;
    int r;

    int sm = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void enable(int I)
    {
        if(l == r) sm = 1;
        else
        {
            if(I <= (l+r)/2)
                left->enable(I);
            else
                right->enable(I);

            sm = left->sm + right->sm;
        }
    }

    int rangesum(int L, int R)
    {
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R) return sm;
        else return left->rangesum(L, R) + right->rangesum(L, R);
    }
};


int main()
{
    int N, Q;
    cin >> N >> Q;

    for(int i = 1; i <= N; i++)
    {
        int ct;
        cin >> ct;

        for(int e = 1; e <= ct; e++)
        {
            int c;
            cin >> c;
            edge[i].push_back(c);
        }
        edge[i].push_back(edge[i].front());
        edge[i].pop_front();           //The arrows are rotated, so now we move and THEN the arrow moves.
        init_arrow[i] = edge[i][0];    //The first move we make!!!
        // cerr << "init arrow " << i << " = " << init_arrow[i] << '\n';
    }

    visit[1] = 1;
    // cerr << "parent " << 1 << " = " << parent[1] << '\n';
    dfs1(1);

    for(int i = 2; i <= N; i++)
    {
        while(edge[i].back() != parent[i])
        {
            edge[i].push_back(edge[i].front());
            edge[i].pop_front();
        }
    }
    // cerr << "check\n";
    //
    // for(int i = 1; i <= N; i++)
    // {
    //     // cerr << "i = " << i << '\n';
    //     for(int j: edge[i]) cerr << j << ' ';
    //     cerr << '\n';
    // }

    dfs2(1);

    dfs3(1, 1);


    // for(int i = 0; i < 2*(N-1); i++) cerr << euler[i] << ' ';
    // cerr << '\n';
    // for(int i = 0; i < 2*(N-1); i++) cerr << first_dfs[i] << ' ';
    // cerr << '\n';

    vector<int> first_list[1+N];
    // for(int p = 0; p < 2*(N-1); p++)
    //     first_list[ first_dfs[p] ].push_back(p);

    for(int i = 0; i < 2*(N-1); i++)
        first_list[ first_dfs[i] ].push_back(i);

    deque<query> queries;
    for(int q = 0; q < Q; q++)
    {
        long long K;
        cin >> K;

        queries.push_back(query{K, q});
    }
    // cerr << "queries are: \n";
    // for(query t: queries) cerr << t.K << ' ' << t.i << '\n';
    sort(queries.begin(), queries.end());


    segtree S(0, 2*(N-1));

    long long prev_moves = 0;

    for(int d = 1; d <= N; d++)
    {
        // cerr << "\n\n";
        // cerr << "dfs index = " << d << '\n';
        int ct = 0;
        for(int f: first_list[d])
        {
            S.enable(f);
            ct++;
            // cerr << "f = " << f << '\n';

            // cerr << queries[0].K << ' ' << prev_moves << ' ' << S.rangesum(0, f) << '\n';

            while(!queries.empty() && queries[0].K <= prev_moves + S.rangesum(0, f))
            {
                int lo = 0;
                int hi = f;
                while(lo != hi)
                {
                    int mid = (lo+hi)/2;
                    if(queries[0].K <= prev_moves + S.rangesum(0, mid))
                        hi = mid;
                    else
                        lo = mid+1;
                }
                // cerr << "answering " << queries[0].i << " as " << euler[lo] << '\n';
                answer[queries[0].i] = euler[lo];
                queries.pop_front();
            }
        }
        while(!queries.empty() && queries[0].K <= prev_moves + S.rangesum(0, 2*(N-1)))
        {
            int lo = 0;
            int hi = 2*(N-1);
            while(lo != hi)
            {
                int mid = (lo+hi)/2;
                if(queries[0].K <= prev_moves + S.rangesum(0, mid))
                    hi = mid;
                else
                    lo = mid+1;
            }
            // cerr << "answering " << queries[0].i << " as " << euler[lo] << '\n';
            answer[queries[0].i] = euler[lo];
            queries.pop_front();
        }
        // cerr << curr_sum << '\n';
        // cerr << queries[0].K << ' ' << queries[0].i << '\n';


        prev_moves += S.rangesum(0, 2*(N-1));
    }
    // cerr << "part 2\n";
    long long period = 2*(N-1);

    while(!queries.empty())
    {
        int q = queries[0].i;
        long long K = queries[0].K;
        queries.pop_front();

        K = (K - prev_moves - 1 +  period*(5 * N)) % period;
        // cerr << "K mod = " << K << '\n';
        answer[q] = euler[K];
        // cerr << "answering " << q << " as " << euler[K] << '\n';
    }

    for(int q = 0; q < Q; q++)
    {
        cout << answer[q] << '\n';
    }
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 548336 KB Output is correct
2 Correct 387 ms 552052 KB Output is correct
3 Correct 896 ms 586440 KB Output is correct
4 Correct 4148 ms 842264 KB Output is correct
5 Correct 6595 ms 864880 KB Output is correct
6 Correct 6493 ms 856400 KB Output is correct
7 Correct 1910 ms 604952 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 548296 KB Output is correct
2 Correct 374 ms 548368 KB Output is correct
3 Correct 367 ms 548684 KB Output is correct
4 Correct 371 ms 548808 KB Output is correct
5 Correct 360 ms 548800 KB Output is correct
6 Correct 370 ms 548924 KB Output is correct
7 Correct 395 ms 548768 KB Output is correct
8 Correct 385 ms 548808 KB Output is correct
9 Correct 372 ms 548876 KB Output is correct
10 Correct 393 ms 548880 KB Output is correct
11 Correct 363 ms 548872 KB Output is correct
12 Correct 368 ms 549020 KB Output is correct
13 Correct 378 ms 548964 KB Output is correct
14 Correct 355 ms 548912 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 368 ms 550988 KB Output is correct
2 Correct 452 ms 561728 KB Output is correct
3 Correct 585 ms 576864 KB Output is correct
4 Correct 612 ms 573520 KB Output is correct
5 Correct 2111 ms 749252 KB Output is correct
6 Correct 2264 ms 749860 KB Output is correct
7 Correct 2170 ms 750748 KB Output is correct
8 Correct 2210 ms 751808 KB Output is correct
9 Correct 2381 ms 774388 KB Output is correct
10 Correct 2520 ms 791268 KB Output is correct
11 Correct 1865 ms 836380 KB Output is correct
12 Correct 1783 ms 827924 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 548336 KB Output is correct
2 Correct 387 ms 552052 KB Output is correct
3 Correct 896 ms 586440 KB Output is correct
4 Correct 4148 ms 842264 KB Output is correct
5 Correct 6595 ms 864880 KB Output is correct
6 Correct 6493 ms 856400 KB Output is correct
7 Correct 1910 ms 604952 KB Output is correct
8 Correct 381 ms 548296 KB Output is correct
9 Correct 374 ms 548368 KB Output is correct
10 Correct 367 ms 548684 KB Output is correct
11 Correct 371 ms 548808 KB Output is correct
12 Correct 360 ms 548800 KB Output is correct
13 Correct 370 ms 548924 KB Output is correct
14 Correct 395 ms 548768 KB Output is correct
15 Correct 385 ms 548808 KB Output is correct
16 Correct 372 ms 548876 KB Output is correct
17 Correct 393 ms 548880 KB Output is correct
18 Correct 363 ms 548872 KB Output is correct
19 Correct 368 ms 549020 KB Output is correct
20 Correct 378 ms 548964 KB Output is correct
21 Correct 355 ms 548912 KB Output is correct
22 Correct 368 ms 550988 KB Output is correct
23 Correct 452 ms 561728 KB Output is correct
24 Correct 585 ms 576864 KB Output is correct
25 Correct 612 ms 573520 KB Output is correct
26 Correct 2111 ms 749252 KB Output is correct
27 Correct 2264 ms 749860 KB Output is correct
28 Correct 2170 ms 750748 KB Output is correct
29 Correct 2210 ms 751808 KB Output is correct
30 Correct 2381 ms 774388 KB Output is correct
31 Correct 2520 ms 791268 KB Output is correct
32 Correct 1865 ms 836380 KB Output is correct
33 Correct 1783 ms 827924 KB Output is correct
34 Correct 1552 ms 574348 KB Output is correct
35 Correct 2023 ms 587200 KB Output is correct
36 Correct 3066 ms 604264 KB Output is correct
37 Correct 5048 ms 774832 KB Output is correct
38 Correct 5544 ms 775652 KB Output is correct
39 Correct 6452 ms 777092 KB Output is correct
40 Correct 6004 ms 779492 KB Output is correct
41 Correct 7849 ms 806004 KB Output is correct
42 Correct 7427 ms 856344 KB Output is correct
43 Correct 6025 ms 863676 KB Output is correct
44 Correct 6088 ms 855332 KB Output is correct
45 Correct 4747 ms 808136 KB Output is correct
46 Correct 395 ms 548328 KB Output is correct