oj.uz

Submission #736150

# Submission time Handle Problem Language Result Execution time Memory
736150 2023-05-05T09:06:58 Z marvinthang Političari (COCI20_politicari) C++17
70 / 70
 251 ms 119948 KB 
/******************************
*    author : @marvinthang    *
*    date : 14 / 11 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false);\
                     cin.tie(NULL);\
                     //cout.tie(NULL);
#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);

const       int MOD = 1e9 + 7; // 998244353;
const     double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e18;
const       int MAX = 505;
const       int LOG = 60;

int N;
pair <int, int> rmq[MAX][MAX][LOG];
long long K;

int main() {
    superspeed;
    cin >> N >> K;
    if (K <= 2) {
        cout << K;
        return 0;
    }
    K -= 2;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> rmq[i][j][0].first;
            rmq[i][j][0].second = i;
        }
    }
    for (int k = 1; k < LOG; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                pair <int, int> tmp = rmq[i][j][k - 1];
                rmq[i][j][k] = rmq[tmp.first][tmp.second][k - 1];
            }
        }
    }
//    cout << rmq[1][2][0].second << '\n';
    pair <int, int> res = {2, 1};
    for (int k = 0; k < LOG; ++k) {
        if ((K >> k) & 1) res = rmq[res.first][res.second][k];
//        cout << res.first << ' ' << res.second << '\n';
    }
    cout << res.first;
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 25 ms 23440 KB Output is correct
3 Correct 150 ms 76480 KB Output is correct
4 Correct 190 ms 97916 KB Output is correct
5 Correct 251 ms 119888 KB Output is correct
6 Correct 217 ms 119784 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 11 ms 9300 KB Output is correct
9 Correct 30 ms 26516 KB Output is correct
10 Correct 188 ms 97888 KB Output is correct
11 Correct 242 ms 119756 KB Output is correct
12 Correct 247 ms 119948 KB Output is correct
13 Correct 1 ms 1748 KB Output is correct
14 Correct 10 ms 9300 KB Output is correct