Submission #344888

#	Time	Username	Problem	Language	Result	Execution time	Memory
344888		limabeans	Političari (COCI20_politicari)	C++17	35 / 70	1115 ms	396664 KiB

politicari

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 505;

int n; ll k;
int g[maxn][maxn];
int dp[maxn][maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    
    cin>>n>>k;
    for (int i=1; i<=n; i++) {
	for (int j=1; j<=n; j++) {
	    cin>>g[i][j];
	}
    }

    if (k==1) out(1);

    
    assert(k>=2);
    memset(dp, -1, sizeof(dp));
    

    vector<int> stk = {-1, 1, 2};
    int idx = 2;
    while (idx<k) {
	int p = stk[idx-1];
	int at = stk[idx];
	assert(p!=at);
	
	if (dp[p][at] == -1) {
	    //dp[p][at] = idx;
	    stk.push_back(g[at][p]);
	} else {
	    //cout<<"HERE"<<endl;
	    assert(k>idx);
	    ll rem = k-idx-1;
	    ll len = idx-dp[p][at]+1;
	    rem %= len;
	    ll x = dp[p][at]+1+rem;
	    out(stk[x]);
	    
	}
	++idx;
    }

    cout<<stk.back()<<endl;    
    return 0;
}

• Subtask 1: 35 / 70