oj.uz

Submission #848292

# Submission time Handle Problem Language Result Execution time Memory
848292 2023-09-12T02:42:06 Z fcmalkcin Političari (COCI20_politicari) C++17
70 / 70
 13 ms 3160 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define eb  emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"

const int maxn = 5e2 + 10;  // Giữ nguyên định nghĩa maxn
const ll mod = 1e9 + 7;
const ll base = 1e18;

int n;
int a[maxn][maxn], f[maxn][maxn], dp[maxn * maxn];

ll k;

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

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            --a[i][j];
        }
    }

    int prev = 0, curr = 1;
    dp[1] = 0;
    dp[2] = 1;
    f[prev][curr] = 2;
    for (int i = 3; (ll)i <= k; ++i) {
        int nxt = a[curr][prev];
        prev = curr;
        curr = nxt;
        if (f[prev][curr] == 0) {
            f[prev][curr] = i;
            dp[i] = curr;
            continue;
        }
        int j = f[prev][curr];
        int cycle = i - j;
        int ret = j + ((k - j) % cycle);
        cout << dp[ret] + 1 << endl;
        return 0;
    }

    cout << dp[k] + 1 << endl;
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 8 ms 2908 KB Output is correct
4 Correct 10 ms 3160 KB Output is correct
5 Correct 12 ms 3160 KB Output is correct
6 Correct 12 ms 3160 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 3 ms 2648 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 13 ms 3160 KB Output is correct
12 Correct 12 ms 3160 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 2 ms 2392 KB Output is correct