oj.uz

Submission #635657

# Submission time Handle Problem Language Result Execution time Memory
635657 2022-08-26T15:26:31 Z jhnah917 Through Another Maze Darkly (CCO21_day1problem3) C++14
0 / 25
 89 ms 35516 KB 
#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];
vector<int> G[80808];
vector<pair<int,int>> Tour;
vector<int> Idx[808080]; // Idx[t] : t에 켜지는 정점
ll TourSize[808080];

void Add(int x, int v){ for(x+=3; x<SZ; x+=x&-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }
int Kth(int x){
    int l = 0, r = Tour.size() - 1;
    while(l < r){
        int m = (l + r) / 2;
        if(Get(m) >= x) r = m;
        else l = m + 1;
    }
    return r;
}

void GetTime(int v, int b=-1, int t=1){
    On[v] = t;
    int pos = find(G[v].begin(), G[v].end(), b) - G[v].begin();
    for(int i=0; i<pos; i++) GetTime(G[v][i], v, t);
    for(int i=pos+1; i<G[v].size(); i++) GetTime(G[v][i], v, t+1);
    if(b != -1) rotate(G[v].begin(), G[v].begin()+pos, G[v].end());
}

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

void GetTour(int v, int b=-1){
    for(auto i : G[v]) if(i != b) AddEdge(v, i), GetTour(i, v), 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());
    }
    GetTime(1);
    GetTour(1);
    for(int i=1; i<=N; i++) TourSize[i] = TourSize[i-1] + Idx[i].size();
    for(int i=1; i<=N; i++) TourSize[i] += TourSize[i-1];

    vector<tuple<ll,ll,ll>> V; // iteration, kth, idx
    for(int q=1; q<=Q; q++){
        ll K; cin >> K;
        int it = lower_bound(TourSize+1, TourSize+N+1, K) - TourSize;
        K -= TourSize[it-1];
        if(it == N+1) K = (K - 1) % TourSize[N] + 1;
        V.emplace_back(it, K, q);
    }
    sort(V.begin(), V.end());

    for(int it=1, i=0; it<=N+1; it++){
        for(auto e : Idx[it]) Add(e, 1);
        while(i < V.size() && get<0>(V[i]) == it){
            R[get<2>(V[i])] = Kth(get<1>(V[i]));
            i += 1;
        }
    }
    for(int i=1; i<=Q; i++) cout << Tour[R[i]].second << "\n";
}

Compilation message

Main.cpp: In function 'void GetTime(int, int, int)':
Main.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=pos+1; i<G[v].size(); i++) GetTime(G[v][i], v, t+1);
      |                      ~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         while(i < V.size() && get<0>(V[i]) == it){
      |               ~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 21400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22444 KB Output is correct
2 Correct 41 ms 27568 KB Output is correct
3 Incorrect 89 ms 35516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21204 KB Output isn't correct
2 Halted 0 ms 0 KB -