oj.uz

답안 #319461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319461 2020-11-05T10:43:31 Z ronnith Političari (COCI20_politicari) C++14
70 / 70
 20 ms 3564 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL 
	#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
	#define dbg2(a,b) dbg(a);dbg(b)
	#define dbg3(a,b,c) dbg2(a,b);dbg(c)
	#define dln cerr << ln
#else
	#define dbg(x) 0
	#define dbg2(a,b) 0
	#define dbg3(a,b,c) 0
	#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;

template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

/*OUTPUT

*/

ll n,k;
ll a[500][500];
bool vis[500][500];
vector<pii> cycle;
pii start;

void dfs(int i,int j){
	if(vis[i][j]){
		start = mk(i,j);
		return;
	}
	cycle.pb(mk(i,j));
	vis[i][j] = true;
	dfs(a[i][j] - 1,i);
}

void solve(){
	cin >> n >> k;
	rep(i,0,n){
		rep(j,0,n){
			cin >> a[i][j];
			vis[i][j] = false;
		}
	}
	if(k == 1){
		cout << 1 << ln;
		return;
	}
	k --;
	// dbg("yes");
	dfs(1,0);
	int time = 0;
	for(auto e:cycle){
		if(e != start){
			time ++;
		}
		else{
			break;
		}
	}
	int cl = sz(cycle) - time;
	// dbg(cl);
	// dbg(time);
	// dbg(k);
	if(k <= time){
		// dbg("yes");
		cout << cycle[k - 1].f + 1 << ln;
	}
	else{
		k --;
		cout << cycle[(k - time) % cl + time].f + 1 << ln;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		solve();
	}
}

Compilation message

politicari.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 1644 KB Output is correct
3 Correct 14 ms 2668 KB Output is correct
4 Correct 16 ms 3052 KB Output is correct
5 Correct 20 ms 3436 KB Output is correct
6 Correct 20 ms 3436 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 17 ms 3308 KB Output is correct
11 Correct 20 ms 3436 KB Output is correct
12 Correct 20 ms 3564 KB Output is correct
13 Correct 1 ms 620 KB Output is correct
14 Correct 2 ms 1004 KB Output is correct