oj.uz

Submission #696393

# Submission time Handle Problem Language Result Execution time Memory
696393 2023-02-06T11:15:44 Z Cross_Ratio Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 9000 ms 25488 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);
    }
}
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);
    int ma = 0;
    for(i=0;i<Q;i++) {
        int a;
        cin >> a;
        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;
    while(cnt <= ma) {
        cnt++;
        int p2 = adj[pt][num[pt]];
        num[pt] = (num[pt] + 1) % adj[pt].size();
        pt = p2;
        while(qt < Query.size() && Query[qt][0]==cnt) {
            ans[Query[qt][1]] = pt;
            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:74:18: 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]
   74 |         while(qt < Query.size() && Query[qt][0]==cnt) {
      |               ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 475 ms 19880 KB Output is correct
3 Execution timed out 9069 ms 25488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 12 ms 19308 KB Output is correct
3 Correct 18 ms 19232 KB Output is correct
4 Correct 44 ms 19264 KB Output is correct
5 Correct 45 ms 19288 KB Output is correct
6 Correct 44 ms 19284 KB Output is correct
7 Correct 44 ms 19284 KB Output is correct
8 Correct 44 ms 19276 KB Output is correct
9 Correct 48 ms 19284 KB Output is correct
10 Correct 52 ms 19172 KB Output is correct
11 Correct 53 ms 19272 KB Output is correct
12 Correct 30 ms 19156 KB Output is correct
13 Correct 30 ms 19276 KB Output is correct
14 Correct 11 ms 19284 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19568 KB Output is correct
2 Correct 65 ms 21168 KB Output is correct
3 Execution timed out 9025 ms 23392 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 19028 KB Output is correct
2 Correct 475 ms 19880 KB Output is correct
3 Execution timed out 9069 ms 25488 KB Time limit exceeded
4 Halted 0 ms 0 KB -