oj.uz

Submission #732191

# Submission time Handle Problem Language Result Execution time Memory
732191 2023-04-28T15:47:17 Z Koful123 Političari (COCI20_politicari) C++17
30 / 70
 21 ms 8504 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void solve(){

	int n,k;
	cin >> n >> k; --k;

	vector<vector<int>> v(n),vis(n);
	for(int i = 0; i < n; i++){
		v[i].assign(n,0); vis[i].assign(n,-1);
		for(int j = 0; j < n; j++){
			cin >> v[i][j];
		}
	}

	vector<int> cyc(1,0);

	int last = 0,cur = 1;
	while(vis[last][cur] == -1){
		vis[last][cur] = cyc.size() - 1;
		cyc.push_back(cur);
		int tmp = last; last = cur;
		cur = v[cur][tmp] - 1;	
	}

	assert(k <= 1e5);

	cyc.pop_back();
	if(k <= vis[last][cur]){
		cout << 1 + cyc[vis[last][cur]] << endl;
		return;
	}

	else k -= vis[last][cur];

	vector<int> nw;
	for(int i = vis[last][cur]; i < cyc.size(); i++){
		nw.push_back(cyc[i]);
	}

	cout << 1 + nw[k % nw.size()] << endl;
}
 
signed main(){ 

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

Compilation message

politicari.cpp: In function 'void solve()':
politicari.cpp:45:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = vis[last][cur]; i < cyc.size(); i++){
      |                              ~~^~~~~~~~~~~~

Subtask #1
30.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 4 ms 2004 KB Execution killed with signal 6
3 Runtime error 13 ms 5568 KB Execution killed with signal 6
4 Runtime error 17 ms 6912 KB Execution killed with signal 6
5 Runtime error 21 ms 8504 KB Execution killed with signal 6
6 Runtime error 19 ms 8472 KB Execution killed with signal 6
7 Incorrect 0 ms 212 KB Output isn't correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 13 ms 3412 KB Output is correct
11 Correct 15 ms 4180 KB Output is correct
12 Correct 16 ms 4180 KB Output is correct
13 Runtime error 1 ms 596 KB Execution killed with signal 6
14 Runtime error 2 ms 980 KB Execution killed with signal 6