oj.uz

Submission #201013

# Submission time Handle Problem Language Result Execution time Memory
201013 2020-02-09T05:35:55 Z dolphingarlic Političari (COCI20_politicari) C++14
70 / 70
 25 ms 1656 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int a[501][501], nxt[501][501];
bool visited[501][501];

vector<int> tail, cycle;

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll m;
    cin >> n >> m;
    FOR(i, 1, n + 1) FOR(j, 1, n + 1) cin >> a[i][j];

    pair<int, int> curr = {1, 2};
    while (true) {
        if (visited[curr.second][curr.first]) {
            pair<int, int> here = {1, 2};
            tail.push_back(1);
            while (here != curr) {
                tail.push_back(here.second);
                here = {here.second, a[here.second][here.first]};
            }
            cycle.push_back(here.second);
            here = {here.second, a[here.second][here.first]};
            while (here != curr) {
                cycle.push_back(here.second);
                here = {here.second, a[here.second][here.first]};
            }
            break;
        } else {
            visited[curr.second][curr.first] = true;
            curr = {curr.second, a[curr.second][curr.first]};
        }
    }

    if (m <= tail.size()) cout << tail[m - 1];
    else cout << cycle[(m - tail.size() - 1) % cycle.size()];
    return 0;
}

Compilation message

politicari.cpp: In function 'int main()':
politicari.cpp:41:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (m <= tail.size()) cout << tail[m - 1];
         ~~^~~~~~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 888 KB Output is correct
3 Correct 17 ms 1272 KB Output is correct
4 Correct 21 ms 1400 KB Output is correct
5 Correct 24 ms 1656 KB Output is correct
6 Correct 22 ms 1528 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 9 ms 888 KB Output is correct
10 Correct 20 ms 1400 KB Output is correct
11 Correct 24 ms 1528 KB Output is correct
12 Correct 25 ms 1528 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 6 ms 632 KB Output is correct