oj.uz

답안 #508837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508837 2022-01-13T21:34:41 Z ETK Through Another Maze Darkly (CCO21_day1problem3) C++14
4 / 25
 206 ms 130804 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,4e6){
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 125452 KB Output is correct
2 Incorrect 94 ms 125836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 125448 KB Output is correct
2 Correct 97 ms 125544 KB Output is correct
3 Correct 110 ms 125512 KB Output is correct
4 Correct 107 ms 125552 KB Output is correct
5 Correct 115 ms 125584 KB Output is correct
6 Correct 104 ms 125616 KB Output is correct
7 Correct 104 ms 125628 KB Output is correct
8 Correct 106 ms 125536 KB Output is correct
9 Correct 122 ms 125500 KB Output is correct
10 Correct 113 ms 125644 KB Output is correct
11 Correct 111 ms 125508 KB Output is correct
12 Correct 97 ms 125628 KB Output is correct
13 Correct 109 ms 125716 KB Output is correct
14 Correct 118 ms 125548 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 125880 KB Output is correct
2 Correct 187 ms 128196 KB Output is correct
3 Incorrect 206 ms 130804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 125452 KB Output is correct
2 Incorrect 94 ms 125836 KB Output isn't correct
3 Halted 0 ms 0 KB -