Submission #201783

#	Time	Username	Problem	Language	Result	Execution time	Memory
201783		EmmanuelAC	Političari (COCI20_politicari)	C++14	70 / 70	24 ms	2424 KiB

politicari

#include <bits/stdc++.h>
#define ll long long
#define REP(i,n) for(int i=0; i<n; i++)
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

long long N, K;
int Mat[1000][1000];
map< pii, int> MAP;

int main()
{

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

    cin >> N >> K;
    REP(i, N)
        REP(j, N)
            cin >> Mat[i][j];

    if(K <= 2){
        cout << K;
        return 0;
    }

    K-= 2;
    pii par = mp(1, 2);
    //cout  << "PAR: " << par.fi << " " << par.se << "\n";
    long long Time = 0;
    while(K > 0 && MAP.find(par)==MAP.end()){
        MAP[par] = Time++;
        int prev = par.se;
        int curr = Mat[par.se-1][par.fi-1];
        par = mp(prev, curr);
        //cout  << "PAR: " << par.fi << " " << par.se << "\n";
        K--;
    }

    //cout << "FISH " << K << "\n";
    //return 0;

    if(K == 0){
        cout << par.se << "\n";
        return 0;
    }

    //cout << "KK: " << K << "\n";

    long long l = Time - MAP[par];
    //cout << "L = " << l << "\n";
    K -= (K/l)*l;

    //cout << "K = " << K << "\n";
    while(K > 0){
        int prev = par.se;
        int curr = Mat[par.se-1][par.fi-1];
        par = mp(prev, curr);
        //cout  << "PAR: " << par.fi << " " << par.se << "\n";
        K--;
    }

    cout << par.se << "\n";

    return 0;
}

• Subtask 1: 70 / 70