oj.uz

Submission #848291

# Submission time Handle Problem Language Result Execution time Memory
848291 2023-09-12T02:38:15 Z fcmalkcin Političari (COCI20_politicari) C++17
70 / 70
 15 ms 3208 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 = 505;  // Thay đổi thành const int
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 2648 KB Output is correct
3 Correct 8 ms 2908 KB Output is correct
4 Correct 10 ms 3164 KB Output is correct
5 Correct 12 ms 3160 KB Output is correct
6 Correct 12 ms 3160 KB Output is correct
7 Correct 1 ms 2592 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 4 ms 2648 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 15 ms 3160 KB Output is correct
12 Correct 13 ms 3208 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct