Submission #295511

#	Time	Username	Problem	Language	Result	Execution time	Memory
295511		patrikpavic2	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	1190 ms	100164 KiB

space_pirate

#include <cstdio>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 3e3 + 50;
const int LOG = 62;

int dis[N][N], udem[N], kor[N][N];
int bio[N], cnt[N], P[N], klsk, cik[N];

int n;
ll k;


void precompute(int x){
	memset(bio, 0, sizeof(bio));
	int cur = x, cdis = 0;
	while(!bio[cur]){
		kor[x][cdis] = cur;
		bio[cur] = 1;
		dis[x][cur] = cdis++;
		cur = P[cur]; 
	}
	udem[x] = cur;
	if(cur == x)
		cik[x] = cdis;
}

int main(){
	memset(dis, -1, sizeof(dis));
	scanf("%d%lld", &n, &k);
	for(int i = 1;i <= n;i++)
		scanf("%d", P + i);
	for(int i = 1;i <= n;i++)
		precompute(i);
	int koji_kl = (k - dis[1][udem[1]]) % cik[udem[1]];
	klsk = kor[udem[1]][koji_kl]; 
	for(int a = 1;a <= n;a++){
		for(int b = 1;b <= n;b++){
			if(dis[1][a] == -1){
				cnt[klsk]++;
				continue;
			}
			if(dis[b][a] != -1){
				int koji = (k - dis[1][a]) % (dis[b][a] + 1);
				if(koji == 0)
					cnt[a]++;
				else
					cnt[kor[b][koji - 1]]++;
			}
			else{
				int koji = (k - dis[1][a] - 1 - dis[b][udem[b]]) % cik[udem[b]];
				cnt[kor[udem[b]][koji]]++;
			}
		}
	}
	for(int i = 1;i <= n;i++)
		printf("%d\n", cnt[i]);	
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
space_pirate.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   scanf("%d", P + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20