Submission #478803

#	Time	Username	Problem	Language	Result	Execution time	Memory
478803		blue	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	7849 ms	864880 KiB

Main

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 12 / 12
• Subtask 4: 5 / 5