oj.uz

Submission #508834

# Submission time Handle Problem Language Result Execution time Memory
508834 2022-01-13T21:25:39 Z ETK Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 207 ms 223576 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=4e6+5,P = 1e9 + 7;
int n,q,c[N],tot,ans[N],now[N],lst[N];
vector <int> G[N];
int main(){
    n = read(),q = read();
    rep(i,1,n){
        c[i] = read();
        rep(j,1,c[i]){
            int x = read();
            G[i].pb(x);
        }
    }
    int u = 1;
    rep(i,1,n*n){
        ans[++tot] = u;
        now[u] = (now[u] + 1) % c[u];
        u = G[u][now[u]];
    }
    int T = n,S = 1;
    memset(lst,0x3f,sizeof(lst));
    rep(i,1,tot){
        if(T < i - lst[ans[i]]){
            S = lst[ans[i]];
            T = i - lst[ans[i]];
        }
        lst[ans[i]] = i;
    }
    while(q--){
        ll k = read() + 1;
        if(k <= tot)cout << ans[k] << '\n';
        else{
            k = (k - S) % T + S;
            cout << ans[k] << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 109856 KB Output is correct
2 Runtime error 163 ms 223576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109884 KB Output is correct
2 Correct 48 ms 110276 KB Output is correct
3 Correct 62 ms 113860 KB Output is correct
4 Correct 104 ms 125700 KB Output is correct
5 Correct 106 ms 125608 KB Output is correct
6 Correct 108 ms 125572 KB Output is correct
7 Correct 104 ms 125628 KB Output is correct
8 Correct 109 ms 125636 KB Output is correct
9 Correct 114 ms 125556 KB Output is correct
10 Correct 112 ms 125628 KB Output is correct
11 Correct 116 ms 125748 KB Output is correct
12 Correct 97 ms 125528 KB Output is correct
13 Correct 97 ms 125644 KB Output is correct
14 Correct 118 ms 125636 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 223476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 109856 KB Output is correct
2 Runtime error 163 ms 223576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -