oj.uz

Submission #696392

# Submission time Handle Problem Language Result Execution time Memory
696392 2023-02-06T11:15:04 Z Cross_Ratio Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 9000 ms 28032 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 >= 2*N*N) {
            a = (a - 2*N*N) % (2*(N-1)) + 2*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 10 ms 19028 KB Output is correct
2 Correct 938 ms 20088 KB Output is correct
3 Execution timed out 9030 ms 28032 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 19148 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 34 ms 19264 KB Output is correct
4 Correct 85 ms 19316 KB Output is correct
5 Correct 78 ms 19316 KB Output is correct
6 Correct 81 ms 19304 KB Output is correct
7 Correct 85 ms 19436 KB Output is correct
8 Correct 80 ms 19284 KB Output is correct
9 Correct 89 ms 19324 KB Output is correct
10 Correct 91 ms 19236 KB Output is correct
11 Correct 100 ms 19316 KB Output is correct
12 Correct 48 ms 19312 KB Output is correct
13 Correct 48 ms 19272 KB Output is correct
14 Correct 12 ms 19332 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19620 KB Output is correct
2 Correct 65 ms 21932 KB Output is correct
3 Execution timed out 9021 ms 24652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 938 ms 20088 KB Output is correct
3 Execution timed out 9030 ms 28032 KB Time limit exceeded
4 Halted 0 ms 0 KB -