Submission #501330

#	Time	Username	Problem	Language	Result	Execution time	Memory
501330		inksamurai	Političari (COCI20_politicari)	C++17	45 / 70	15 ms	4548 KiB

politicari

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;

int main(){
_3qplfh5;
	int n,k;
	cin>>n>>k;
	vec(vi) a(n,vi(n));
	rep(i,n){
		rep(j,n){
			cin>>a[i][j];
			a[i][j]--;
		}
	}
	k--;
	vec(vi) usd(n,vi(n));
	vec(pii) way;
	int c=0,nec=1;
	way.pb({c,nec});
	usd[c][nec]=1;
	vec(pii) incyc;
	while(k>0){
		int onec=nec;
		// nec , a[nec][c]
		int nxt=a[nec][c];
		// printf("%d %d\n", nec,nxt);
		if(usd[nec][nxt]){
			pii p={nec,nxt};
			while(sz(way)){
				incyc.pb(way.back());
				if(way.back()==p){
					break;
				}
				way.pop_back();
			}
			break;
		}
		way.pb({nec,nxt});
		usd[nec][nxt]=1;
		nec=a[nec][c];
		c=onec;
		k--;
	}
	if(k==0){
		printf("%d\n", c+1);
		exit(0);
	}
	reverse(all(incyc));
	k--;
	k%=sz(incyc);
	printf("%d\n", incyc[k].fi+1);
//	
	return 0;
}

• Subtask 1: 45 / 70