Submission #229234

#	Time	Username	Problem	Language	Result	Execution time	Memory
229234		VEGAnn	Političari (COCI20_politicari)	C++14	70 / 70	28 ms	3968 KiB

politicari

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 510;
vector<pii> vc, cyc;
ll k;
int n, nt[N][N], mrk[N][N], tim[N][N], tt = 0;

void CYCLE(pii lst){
    cyc.clear();
    vc.PB(MP(-1, -1));

    do {
        vc.pop_back();
        cyc.PB(vc.back());
    } while (vc.back() != lst);

    reverse(all(cyc));

    k -= ll(tim[lst.ft][lst.sd]);
    k %= sz(cyc);

    cout << cyc[k].ft + 1;
    exit(0);
}

void dfs(int x, int y){
    tt++;
    tim[x][y] = tt;

    if (ll(tt) == k){
        cout << x + 1;
        exit(0);
    }

    vc.PB(MP(x, y));
    mrk[x][y] = 1;

    int nw = nt[x][y];

    if (mrk[nw][x] == 0)
        dfs(nw, x); else
    if (mrk[nw][x] == 1)
        CYCLE(MP(nw, x));

    mrk[x][y] = 2;
    vc.pop_back();
}

int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> k;

    if (k == 1){
        cout << 1;
        return 0;
    }
    k--;

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

    dfs(1, 0);

    return 0;
}

• Subtask 1: 70 / 70