oj.uz

답안 #635683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635683 2022-08-26T16:18:55 Z jhnah917 Through Another Maze Darkly (CCO21_day1problem3) C++14
25 / 25
 1953 ms 278832 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[808080];
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) % Tour.size() + 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 << " ";
}

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
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38356 KB Output is correct
2 Correct 29 ms 40840 KB Output is correct
3 Correct 146 ms 64424 KB Output is correct
4 Correct 959 ms 256444 KB Output is correct
5 Correct 1330 ms 278832 KB Output is correct
6 Correct 1301 ms 270404 KB Output is correct
7 Correct 482 ms 93088 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 38356 KB Output is correct
2 Correct 19 ms 38484 KB Output is correct
3 Correct 21 ms 38500 KB Output is correct
4 Correct 20 ms 38596 KB Output is correct
5 Correct 20 ms 38512 KB Output is correct
6 Correct 20 ms 38524 KB Output is correct
7 Correct 22 ms 38632 KB Output is correct
8 Correct 20 ms 38612 KB Output is correct
9 Correct 24 ms 38616 KB Output is correct
10 Correct 26 ms 38676 KB Output is correct
11 Correct 25 ms 38740 KB Output is correct
12 Correct 20 ms 38868 KB Output is correct
13 Correct 22 ms 38884 KB Output is correct
14 Correct 20 ms 38696 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 39484 KB Output is correct
2 Correct 45 ms 44596 KB Output is correct
3 Correct 90 ms 52604 KB Output is correct
4 Correct 76 ms 48256 KB Output is correct
5 Correct 592 ms 114760 KB Output is correct
6 Correct 606 ms 113792 KB Output is correct
7 Correct 627 ms 113828 KB Output is correct
8 Correct 675 ms 122788 KB Output is correct
9 Correct 848 ms 160552 KB Output is correct
10 Correct 888 ms 179556 KB Output is correct
11 Correct 462 ms 229048 KB Output is correct
12 Correct 452 ms 220692 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38356 KB Output is correct
2 Correct 29 ms 40840 KB Output is correct
3 Correct 146 ms 64424 KB Output is correct
4 Correct 959 ms 256444 KB Output is correct
5 Correct 1330 ms 278832 KB Output is correct
6 Correct 1301 ms 270404 KB Output is correct
7 Correct 482 ms 93088 KB Output is correct
8 Correct 19 ms 38356 KB Output is correct
9 Correct 19 ms 38484 KB Output is correct
10 Correct 21 ms 38500 KB Output is correct
11 Correct 20 ms 38596 KB Output is correct
12 Correct 20 ms 38512 KB Output is correct
13 Correct 20 ms 38524 KB Output is correct
14 Correct 22 ms 38632 KB Output is correct
15 Correct 20 ms 38612 KB Output is correct
16 Correct 24 ms 38616 KB Output is correct
17 Correct 26 ms 38676 KB Output is correct
18 Correct 25 ms 38740 KB Output is correct
19 Correct 20 ms 38868 KB Output is correct
20 Correct 22 ms 38884 KB Output is correct
21 Correct 20 ms 38696 KB Output is correct
22 Correct 23 ms 39484 KB Output is correct
23 Correct 45 ms 44596 KB Output is correct
24 Correct 90 ms 52604 KB Output is correct
25 Correct 76 ms 48256 KB Output is correct
26 Correct 592 ms 114760 KB Output is correct
27 Correct 606 ms 113792 KB Output is correct
28 Correct 627 ms 113828 KB Output is correct
29 Correct 675 ms 122788 KB Output is correct
30 Correct 848 ms 160552 KB Output is correct
31 Correct 888 ms 179556 KB Output is correct
32 Correct 462 ms 229048 KB Output is correct
33 Correct 452 ms 220692 KB Output is correct
34 Correct 453 ms 72216 KB Output is correct
35 Correct 532 ms 80340 KB Output is correct
36 Correct 689 ms 91752 KB Output is correct
37 Correct 1238 ms 158964 KB Output is correct
38 Correct 1251 ms 159164 KB Output is correct
39 Correct 1286 ms 161084 KB Output is correct
40 Correct 1528 ms 169796 KB Output is correct
41 Correct 1794 ms 213700 KB Output is correct
42 Correct 1953 ms 270464 KB Output is correct
43 Correct 1405 ms 277744 KB Output is correct
44 Correct 1339 ms 269360 KB Output is correct
45 Correct 1628 ms 216716 KB Output is correct
46 Correct 21 ms 38356 KB Output is correct