oj.uz

Submission #544170

# Submission time Handle Problem Language Result Execution time Memory
544170 2022-04-01T09:25:39 Z AlperenT Političari (COCI20_politicari) C++17
70 / 70
 17 ms 3460 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 5;

long long n, k, graph[N][N], dist[N][N];

struct Item{
    long long a, b;
};

Item cur = {1, 2};

bool flag;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> graph[i][j];
        }
    }

    if(k == 1) cout << 1;
    else{
        dist[1][2] = 2, k -= 2;

        while(k > 0){
            k--;

            if(flag) cur = {cur.b, graph[cur.b][cur.a]};
            else{
                if(dist[cur.b][graph[cur.b][cur.a]] == 0){
                    dist[cur.b][graph[cur.b][cur.a]] = dist[cur.a][cur.b] + 1;
                    cur = {cur.b, graph[cur.b][cur.a]};
                }
                else{
                    k %= dist[cur.a][cur.b] - dist[cur.b][graph[cur.b][cur.a]] + 1;
                    cur = {cur.b, graph[cur.b][cur.a]};
                    flag = true;
                }
            }
        }

        cout << cur.b;
    }
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 2004 KB Output is correct
3 Correct 10 ms 2644 KB Output is correct
4 Correct 13 ms 2864 KB Output is correct
5 Correct 16 ms 3112 KB Output is correct
6 Correct 17 ms 3044 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 14 ms 2772 KB Output is correct
11 Correct 16 ms 3460 KB Output is correct
12 Correct 16 ms 3244 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct