oj.uz

Submission #696413

# Submission time Handle Problem Language Result Execution time Memory
696413 2023-02-06T12:49:09 Z Cross_Ratio Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 9000 ms 41140 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> adj[800005];
int num[800005];
void dfs(int c, int p) {
    int i, j;
    if(p == -1) {
        int n = num[c];
        vector<int> V(adj[c].size());
        int sz = adj[c].size();
        for(i=0;i<sz;i++) {
            V[i] = adj[c][(i+n)%sz];
        }
        adj[c] = V;
        num[c] = (num[c] + sz - n) % sz;
    }
    else {
        int n = -1;
        int sz = adj[c].size();
        for(i=0;i<sz;i++) {
            if(adj[c][i]==p) n = i;
        }
        vector<int> V(sz);
        for(i=0;i<sz;i++) {
            V[i] = adj[c][(i+n)%sz];
        }
        adj[c] = V;
        num[c] = (num[c] + sz - n) % sz;
    }
    for(int n : adj[c]) {
        if(n ==p) continue;
        dfs(n, c);
    }
}
int sz[800005];
bool B[800005];
int dfs_cnt = 0;
int A[1600005];
int C[800005];
int par[800005];
int ord[800005];
void dfs2(int c, int p) {
    sz[c] = 1;
    par[c] = p;
    C[c] = dfs_cnt;
    for(int n : adj[c]) {
        if(n==p) continue;
        A[dfs_cnt++] = c;
        dfs2(n, c);
        ord[c]++;
        sz[c] += sz[n];
    }
    if(sz[c] == 1) B[c] = true;
    A[dfs_cnt++] = c;
}
vector<array<int, 2>> Query;
int ans[800005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, Q;
    cin >> N >> Q;
    int i, j;
    for(i=0;i<N;i++) {
        int k;
        cin >> k;
        for(j=0;j<k;j++) {
            int c;
            cin >> c;
            adj[i].push_back(c-1);
        }
        num[i] = 1 % k;
    }
    dfs(0, -1);
    dfs2(0, -1);
    //cout << "dfs done\n";
    int ma = 0;
    for(i=0;i<Q;i++) {
        int a;
        cin >> a;
        //a = i+1;
        if(a >= N*N) {
            a = (a - N*N) % (2*(N-1)) + N*N;
        }
        ma = max(ma, a);
        Query.push_back({a, i});
    }
    sort(Query.begin(),Query.end());
    int pt = 0, cnt = 0;
    int qt = 0;
    for(i=0;i<N;i++) {
        if(B[i] && par[i] != -1) ord[par[i]]--;
    }
    //cout << "Finding Graph\n";
    while(qt < Query.size() && !B[0]) {
        //cout << pt << ' ' << cnt << '\n';
        //for(i=0;i<N;i++) cout << B[i] << ' ';
        //cout << '\n';
        if(B[pt]) {
            //cout << pt << " is ON\n";
            //cout << qt << ' ' << Query[qt][0] << '\n';
            while(qt < Query.size() && Query[qt][0] <= cnt + 2 * (sz[pt]-1)+1) {
                //cout << "qt is " << qt << '\n';
                int v = Query[qt][0] - cnt;
                ans[Query[qt][1]] = A[C[pt]+v];
                //cout << C[pt] + v << " :: " << Query[qt][1] << ' ' << A[C[pt]+v] << '\n';
                qt++;
            }
            cnt += 2*(sz[pt] - 1)+1;
            pt = par[pt];
        }
        else {
            cnt++;
            int p2 = adj[pt][num[pt]];
            num[pt] = (num[pt] + 1) % adj[pt].size();
            if(p2 == par[pt] && ord[pt]==0) {
                B[pt] = true;
                if(par[pt] != -1) ord[par[pt]]--;
            }
            if(p2 == par[pt] && p2 == 0 && ord[0] == 0 && num[0] == 0) {
                B[0] = true;
            }
            pt = p2;
            while(qt < Query.size() && Query[qt][0]==cnt) {
                //cout << "qts is " << qt << '\n';
                ans[Query[qt][1]] = pt;
                qt++;
            }
        }
    }
    while(qt < Query.size()) {
        int v = (Query[qt][0] - cnt) % (2*(N-1));
        ans[Query[qt][1]] = A[v];
        qt++;
    }
    for(i=0;i<Q;i++) cout <<ans[i]+1 << '\n';
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:7:12: warning: unused variable 'j' [-Wunused-variable]
    7 |     int i, j;
      |            ^
Main.cpp: In function 'int main()':
Main.cpp:97:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(qt < Query.size() && !B[0]) {
      |           ~~~^~~~~~~~~~~~~~
Main.cpp:104:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while(qt < Query.size() && Query[qt][0] <= cnt + 2 * (sz[pt]-1)+1) {
      |                   ~~~^~~~~~~~~~~~~~
Main.cpp:126:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             while(qt < Query.size() && Query[qt][0]==cnt) {
      |                   ~~~^~~~~~~~~~~~~~
Main.cpp:133:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     while(qt < Query.size()) {
      |           ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Correct 268 ms 21488 KB Output is correct
3 Execution timed out 9073 ms 41140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19140 KB Output is correct
2 Correct 9 ms 19188 KB Output is correct
3 Correct 12 ms 19312 KB Output is correct
4 Correct 11 ms 19372 KB Output is correct
5 Correct 10 ms 19448 KB Output is correct
6 Correct 11 ms 19412 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 11 ms 19412 KB Output is correct
9 Correct 15 ms 19520 KB Output is correct
10 Correct 21 ms 19448 KB Output is correct
11 Correct 21 ms 19540 KB Output is correct
12 Correct 31 ms 19616 KB Output is correct
13 Correct 21 ms 19636 KB Output is correct
14 Correct 10 ms 19540 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20436 KB Output is correct
2 Correct 67 ms 25604 KB Output is correct
3 Execution timed out 9058 ms 33468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Correct 268 ms 21488 KB Output is correct
3 Execution timed out 9073 ms 41140 KB Time limit exceeded
4 Halted 0 ms 0 KB -