Submission #247402

#	Time	Username	Problem	Language	Result	Execution time	Memory
247402		dvdg6566	Političari (COCI20_politicari)	C++14	70 / 70	25 ms	3456 KiB

politicari

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=510;
const ll MAXK=100000;
const ll INF = 1e9;
const ll MOD = 1e9+7;

ll N,M,K,Q,R,C,a,b,c,OX;
ll A[MAXN][MAXN];
ll B[MAXN][MAXN];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>K;
	if(K==1){cout<<1;return 0;}
	for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)cin>>A[i][j];
	pi t=mp(2,1);
	B[2][1]=1;
	int len=0;
	for(int i=2;i<K;++i){
		int x=A[t.f][t.s];
		t=mp(x,t.f);
		if(B[t.f][t.s]){
			len=i-B[t.f][t.s];
			break;
		}
		B[t.f][t.s]=i;
	}
	if (len){
		int offs=B[t.f][t.s];
		// cout<<len<<'\n';
		K-=(offs+1);
		K%=len;
		for(int i=0;i<K;++i){
			int x=A[t.f][t.s];
			t=mp(x,t.f);
		}
		cout<<t.f;
		return 0;
	}
	cout<<t.f;
}

• Subtask 1: 70 / 70