Submission #114098

#	Time	Username	Problem	Language	Result	Execution time	Memory
114098		gs14004	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	2056 ms	43984 KiB

space_pirate

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 100005;

lint k;
int n, a[MAXN];
int par[60][MAXN];
lint ans[17][MAXN];
int cmp[MAXN];

lint anc(int x, lint k){
	for(int i=0; k; i++){
		if(k & 1){
			x = par[i][x];
		}
		k >>= 1;
	}
	return x;
}

void add_path(int x, int c){
	for(int i=0; c; i++){
		if(c & 1){
			ans[i][x]++;
			x = par[i][x];
		}
		c >>= 1;
	}
}

vector<int> gph[MAXN];
int lvl[MAXN], dep[MAXN];
int num[MAXN];

void dfs(int x){
	for(auto &i : gph[x]){
		lvl[i] = max(lvl[i], lvl[x]);
		dep[i] = dep[x] + 1;
		dfs(i);
	}
}

void dfsCyc(int x, vector<int> &cyc, lint k){
	{
		for(int i=0; i<num[x]; i++){
			auto arrival = k;
			int cycLength = dep[x] + cyc.size() - (num[x] - i) + 1;
			arrival %= cycLength;
			if(arrival <= i){
				ans[0][cyc[arrival]]++;
			}
			else{
				arrival -= i + 1;
				ans[0][anc(x, arrival)]++;
			}
		}
		for(int i=num[x]; i<cyc.size(); i++){
			auto arrival = k - i - 1;
			int cycLength = dep[x] + i - num[x] + 1;
			arrival %= cycLength;
			ans[0][anc(x, arrival)]++;
		}
	}
	for(auto &i : gph[x]){
		if(cmp[i] == 2) continue;
		num[i] = num[x];
		dep[i] = dep[x] + 1;
		dfsCyc(i, cyc, k);
	}
}

void solve_cycle(vector<int> v, lint k){
	for(int i=0; i<v.size(); i++){
		num[v[i]] = i;
	}
	for(auto &i : v){
		dfsCyc(i, v, k);
	}
}

void solve_path(vector<int> v){ // TODO : quadratic
	dep[v.back()] = 1;
	dfs(v.back());
	for(int i=1; i<=n; i++){
		if(!cmp[par[20][i]]) continue;
		int w = v.size() - lvl[i];
		int pos = anc(i, k - w);
		add_path(pos, w);
		for(int j = 1; j <= lvl[i]; j++){
			lint upV = k - (lvl[1] - j + 1);
			upV %= (dep[i] - j + 1);
			ans[0][anc(i, upV)]++;
		}
	}
}

int main(){
	scanf("%d %lld",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		gph[a[i]].push_back(i);
	}
	memcpy(par[0], a, sizeof(par[0]));
	for(int i=1; i<60; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	for(int i=1; cmp[i]<2; i=a[i]) cmp[i]++;
	int pthcnt = n - count(cmp + 1, cmp + n + 1, 0);
	int onecnt = count(cmp + 1, cmp + n + 1, 1);
	ans[0][anc(1, k)] += 1ll * n * (n - pthcnt);
	for(int i=1; i<=n; i++){
		if(!cmp[par[20][i]]){
			int pos = anc(i, k - pthcnt);
			add_path(pos, pthcnt);
		}
	}
	vector<int> pth;
	vector<int> cyc;
	for(int i=1; ; i=a[i]){
		if(cmp[i] == 1){
			lvl[i] = onecnt - pth.size();
			pth.push_back(i);
		}
		if(cmp[i] == 2){
			if(cyc.size() && i == cyc.front()) break;
			cyc.push_back(i);
		}
	}
	if(pth.size()) solve_path(pth);
	solve_cycle(cyc, k - pth.size());
	for(int i=16; i; i--){
		for(int j=1; j<=n; j++){
			ans[i - 1][par[i - 1][j]] += ans[i][j];
			ans[i - 1][j] += ans[i][j];
		}
	}
	for(int i=1; i<=n; i++) printf("%lld\n", ans[0][i]);
}

Compilation message (stderr)

space_pirate.cpp: In function 'void dfsCyc(int, std::vector<int>&, lint)':
space_pirate.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=num[x]; i<cyc.size(); i++){
                     ~^~~~~~~~~~~
space_pirate.cpp: In function 'void solve_cycle(std::vector<int>, lint)':
space_pirate.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~~
space_pirate.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

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