Submission #114279

#	Time	Username	Problem	Language	Result	Execution time	Memory
114279		gs14004	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	2052 ms	46792 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);
	}
}

namespace Case1{
	vector<int> tr[MAXN];
	int dep[MAXN];
	bool inCyc[MAXN];
	void add_edge(int s, int e){
		tr[s].push_back(e);
	}
	void dfs(int x){
		for(auto &i : tr[x]){
			dep[i] = dep[x] + 1;
			dfs(i);
		}
	}
	int dfs2(int pos, int startDep, int endDep){
		int ret = 0;
		if(dep[pos] < endDep && dep[pos] >= startDep) ret++;
		for(auto &i : tr[pos]) ret += dfs2(i, startDep, endDep);
		if(dep[pos] == startDep) ans[0][pos] += ret;
		return ret;
	}
	int dfs3(int pos, int startDep, int endDep, int sgn = +1){
		int ret = 0;
		if(dep[pos] < endDep && dep[pos] >= startDep) ret++;
		for(auto &i : tr[pos]){
			if(!inCyc[i]){
				ret += dfs3(i, startDep, endDep, sgn);
			}
		}
		if(dep[pos] == startDep) ans[0][pos] += ret * sgn;
		return ret;
	}
	int dfs4(int pos, int startDep, int endDep){
		int ret = 0;
		if(dep[pos] < endDep && dep[pos] >= startDep) ret++;
		for(auto &i : tr[pos]){
			if(!inCyc[i]){
				ret += dfs4(i, startDep, endDep);
			}
		}
		return ret;
	}
	void solve(vector<int> cyc, lint k){
		for(auto &i : cyc) inCyc[i] = 1;
		for(int i=0; i+1<cyc.size(); i++){
			tr[cyc[i+1]].push_back(cyc[i]);
		}
		dfs(cyc.back());
		// beautiful case
		for(int i = 2; i<=cyc.size(); i++){
			int original_pinpoint = k % i;
			dfs2(cyc.back(), i - k % i - 1, i - 1);
			ans[0][cyc[original_pinpoint]] += dfs2(cyc.back(), -1, i - k % i - 1);
		}
		// ugly case
		for(int i = cyc.size() + 1; i <= n; i++){
			int d = i - cyc.size();
			for(int j = 0; j < cyc.size(); j++){
				int stDep = dep[cyc[j]] + d;
				stDep = max(stDep * 1ll, i - 1 - k % i);
				if(dep[cyc[j]] <= i - 1 - k % i){
					dfs3(cyc[j], i - 1 - k % i, i - 1, +1);
					dfs3(cyc[j], i - 1 - k % i, stDep, -1);
				}
				else{
					int fuck = dfs4(cyc[j], stDep, i - 1);
					ans[0][cyc[cyc.size() - i + k % i]] += fuck;
				}
				if(k % i < cyc.size()){
					ans[0][cyc[k % i]] += dfs4(cyc[j], dep[cyc[j]] + d, stDep);
				}
			}
		}
	}
}

/// tree T
/// query가 한 nlogn 개 정도 있는데
/// Q(i, j) <- depth = i인 노드들에 대해, 
/// 해당 노드의 subtree중 depth가 j 이하인 것들의 개수를 
/// 다 그 노드에 대응되는 배열에 더해줌

void dfsCyc(int x, vector<int> &cyc, lint k){
	{
		// TODO: quadratic <- case 1
		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;
		Case1::add_edge(x, i);
		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);
	}
	Case1::solve(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++){ // case 3
			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 Case1::solve(std::vector<int>, lint)':
space_pirate.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i+1<cyc.size(); i++){
                ~~~^~~~~~~~~~~
space_pirate.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 2; i<=cyc.size(); i++){
                  ~^~~~~~~~~~~~
space_pirate.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < cyc.size(); j++){
                   ~~^~~~~~~~~~~~
space_pirate.cpp:113:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(k % i < cyc.size()){
        ~~~~~~^~~~~~~~~~~~
space_pirate.cpp: In function 'void dfsCyc(int, std::vector<int>&, lint)':
space_pirate.cpp:130: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:148: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:174: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:176: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