Submission #635681

#	Time	Username	Problem	Language	Result	Execution time	Memory
635681		jhnah917	Through Another Maze Darkly (CCO21_day1problem3)	C++14	4 / 25	92 ms	46732 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 21;

int N, Q, On[808080], R[808080], T[SZ<<1];
vector<int> G[80808];
vector<pair<int,int>> Tour;
vector<int> Idx[808080]; // Idx[t] : t에 켜지는 정점

void Add(int x, int v){
    for(x|=SZ; x; x>>=1) T[x] += 1;
}
int Kth(int k){
    int x = 1;
    while(x < SZ){
        if(k <= T[x<<1]) x = x << 1;
        else k -= T[x<<1], x = x << 1 | 1;
    }
    return x ^ SZ;
}

inline void AddEdge(int s, int e){
    Idx[max(On[s], On[e])].push_back(Tour.size());
    Tour.emplace_back(s, e);
}

void DFS(int v, int b=-1, int t=1){
    On[v] = t;
    bool flag = false;
    for(auto i : G[v]){
        if(i == b) flag = true;
        else if(flag) On[i] = t + 1, AddEdge(v, i), DFS(i, v, t+1), AddEdge(i, v);
    }
    for(auto i : G[v]){
        if(i == b) break;
        else On[i] = t, AddEdge(v, i), DFS(i, v, t), AddEdge(i, v);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        int sz; cin >> sz; G[i].resize(sz);
        for(auto &j : G[i]) cin >> j;
        rotate(G[i].begin(), G[i].begin()+1, G[i].end());
    }
    DFS(1);

    vector<pair<ll,ll>> V(Q);
    for(int i=0; i<Q; i++) cin >> V[i].first, V[i].second = i + 1;
    sort(V.begin(), V.end());

    ll now = 0;
    for(int i=0, j=1; i<V.size(); i++){
        for(; j<=N && now<V[i].first; j++){
            for(auto e : Idx[j]) Add(e, 1);
            now += T[1];
        }
        ll k = V[i].first - (now - T[1]);
        R[V[i].second] = Kth((k - 1) % (2*N-2) + 1);
    }
    for(int i=1; i<=Q; i++) cout << Tour[R[i]].second << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0, j=1; i<V.size(); i++){
      |                       ~^~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5