oj.uz

Submission #247402

# Submission time Handle Problem Language Result Execution time Memory
247402 2020-07-11T10:28:22 Z dvdg6566 Političari (COCI20_politicari) C++14
70 / 70
 25 ms 3456 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 9 ms 2048 KB Output is correct
3 Correct 16 ms 2688 KB Output is correct
4 Correct 20 ms 2944 KB Output is correct
5 Correct 23 ms 3200 KB Output is correct
6 Correct 24 ms 3072 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 9 ms 2176 KB Output is correct
10 Correct 21 ms 2944 KB Output is correct
11 Correct 24 ms 3456 KB Output is correct
12 Correct 25 ms 3456 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 6 ms 1280 KB Output is correct