Submission #113477

#	Time	Username	Problem	Language	Result	Execution time	Memory
113477		cki86201	Space Pirate (JOI14_space_pirate)	C++11	100 / 100	825 ms	99056 KiB

space_pirate

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

ll ans[100010];
int N, A[100010];
ll K;

vector<int> Tail, Cycle;
int chk_cycle[100010];

vector <int> Rev_A[100010];
int pp[100010]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int color[100010];

namespace Case_1 {
ll T[100010];
int cycle_len;
void dfs(int x, int idx, int L, int depth) {
T[0] += L / cycle_len;
if(L % cycle_len) {
int lv = (idx + K - L - depth) % cycle_len;
int rv = (idx + K - 1 - depth) % cycle_len;
T[lv]++; T[rv+1]--;
if(lv > rv) T[0]++;
}
for(int e : Rev_A[x]) if(chk_cycle[e] == 0) {
dfs(e, idx, L, depth + 1);
}
}
void Do(int x, int L) {
vector <int> cycle;
cycle.pb(x);
for(int t=A[x];t!=x;t=A[t]) cycle.pb(t);
for(int e : cycle) color[e] = 1;
int m = szz(cycle);
cycle_len = m;
rep(i, m+2) T[i] = 0;
rep(i, m) {
dfs(cycle[i], i, L, 0);
}
for(int i=1;i<m;i++) T[i] += T[i-1];
rep(i, m) ans[cycle[i]] += T[i];
}
}

vector <int> Path, VList;
int Num_Path[100010];
int Cycle_len;
int Path_len;
namespace Case_2 {
vector <int> VListC2;
int Depth[100010] = {};
int Sub_cnt[100010] = {};
int Tree_up[100010][20];
int Chk_L2[100010];
void dfs(int x) {
for(int e : Rev_A[x]) if(Num_Path[e] == -1) {
Num_Path[e] = Num_Path[x];
Depth[e] = Depth[x] + 1;
Tree_up[e][0] = x;
for(int i=1;i<20;i++) {
Tree_up[e][i] = Tree_up[ Tree_up[e][i-1] ][i-1];
}
dfs(e);
}
}
void sub_dfs(int x) {
Sub_cnt[x] = 1;
for(int e : Rev_A[x]) if(Chk_L2[e]) {
sub_dfs(e);
Sub_cnt[x] += Sub_cnt[e];
}
}
int Tree_climb(int x, int a) {
rep(i, 20) if(1<<i & a) x = Tree_up[x][i];
return x;
}
	
vector <int> DList[100010];
vector <ll> DSum[100010];
int D_to_Y_temp[200020] = {}; int* D_to_Y = D_to_Y_temp + 100010;
ll sum_D_temp[200020] = {}; ll* sum_D = sum_D_temp + 100010;
ll C1T[100010] = {};
void Do() {
for(int i=1;i<=N;i++) if(Find(i) == Find(1)) VList.pb(i);
for(int e : Tail) Path.pb(e);
for(int e : Cycle) Path.pb(e);
reverse(all(Path));
memset(Num_Path, -1, sizeof Num_Path);
Cycle_len = szz(Cycle);
Path_len = szz(Path);
rep(i, Path_len) Num_Path[ Path[i] ] = i;
rep(i, Path_len) {
int v = Path[i];
Depth[v] = i;
if(i) {
Tree_up[v][0] = Path[i-1];
for(int i=1;i<20;i++) {
Tree_up[v][i] = Tree_up[ Tree_up[v][i-1] ][i-1];
}
}
dfs(v);
}
for(int e : VList) if(Num_Path[e] != Path_len - 1) {
int lv = -1, len = -1;
lv = (-(K - 1 - Depth[e]) % Cycle_len + Cycle_len) % Cycle_len;
if(Num_Path[e] < Cycle_len) {
len = Path_len - Cycle_len;
}
else {
len = Path_len - 1 - Num_Path[e];
}
C1T[0] += len / Cycle_len;
if(len % Cycle_len) {
int rv = (lv + len - 1) % Cycle_len;
C1T[lv]++; C1T[rv+1]--;
if(lv > rv) C1T[0]++;
}
}
for(int i=1;i<Cycle_len;i++) C1T[i] += C1T[i-1];
rep(i, Cycle_len) ans[Path[i]] += C1T[i];
for(int e : VList) if(Num_Path[e] < Cycle_len - 1) VListC2.pb(e), Chk_L2[e] = 1;
int max_depth = -1, max_D = -1;
for(int e : VListC2) max_depth = max(max_depth, Depth[e]);
for(int e : VListC2) {
int d_min = Depth[e] - (Cycle_len - 1);
int d_max = Depth[e] - (Num_Path[e] + 1);
sum_D[d_min]++;
sum_D[d_max+1]--;
max_D = max(max_D, d_max);
}
for(int i=-Cycle_len;i<=max_depth+2;i++) sum_D[i] += sum_D[i-1];
memset(D_to_Y_temp, -1, sizeof D_to_Y_temp);
auto add_event = [&](int y, int d) {
DList[y].pb(d);
D_to_Y[d] = y;
};
for(int D = -(Cycle_len-1); D <= max_D; D++) {
ll NK = K - szz(Tail);
int rlen = Cycle_len + D + 1;
if(NK % rlen == 0);
else {
add_event(rlen - 1 - (NK % rlen), D);
}
}
for(int i=0;i<=max_depth;i++) {
sort(all(DList[i]));
DSum[i].resize(szz(DList[i]));
}
sub_dfs(Path[0]);
for(int e : VListC2) {
int expected_d = Depth[e] - Cycle_len;
int expected_y = D_to_Y[expected_d];
if(expected_y == -1) continue;
if(Depth[e] > expected_y) {
int ue = Tree_climb(e, Depth[e] - expected_y);
ans[ue] -= Sub_cnt[e];
sum_D[expected_d] += Sub_cnt[e];
}
}
for(int e : VListC2) {
int expected_d = Depth[e] - 1 - Num_Path[e];
int expected_y = D_to_Y[expected_d];
if(expected_y == -1 || expected_d == -1) continue;
if(Depth[e] > expected_y) {
int ue = Tree_climb(e, Depth[e] - expected_y);
ans[ue] += Sub_cnt[e];
sum_D[expected_d] -= Sub_cnt[e];
}
}
for(int e : VListC2) {
int expected_d = Depth[e] - Cycle_len;
int depth_e = Depth[e];
int v = (int)(upper_bound(all(DList[depth_e]), expected_d) - DList[depth_e].begin());
if(v) {
DSum[depth_e][0] += Sub_cnt[e];
if(v != szz(DSum[depth_e])) DSum[depth_e][v] -= Sub_cnt[e];
ans[e] -= (ll) v * Sub_cnt[e];
}
}
for(int e : VListC2) {
int expected_d = Depth[e] - 1 - Num_Path[e];
int depth_e = Depth[e];
int v = (int)(upper_bound(all(DList[depth_e]), expected_d) - DList[depth_e].begin());
if(v) {
DSum[depth_e][0] -= Sub_cnt[e];
if(v != szz(DSum[depth_e])) DSum[depth_e][v] += Sub_cnt[e];
ans[e] += (ll) v * Sub_cnt[e];
}
}
for(int i=0;i<=max_depth;i++) {
int m = szz(DSum[i]);
for(int j=1;j<m;j++) DSum[i][j] += DSum[i][j-1];
rep(j, m) sum_D[DList[i][j]] += DSum[i][j];
}
for(int D = -(Cycle_len-1); D <= max_D; D++) if(sum_D[D] > 0) {
int Y = D_to_Y[D];
if(Y == -1) Y = Cycle_len - 1;
else Y -= (D + 1);
ans[Path[Y]] += sum_D[D];
}
}
}

namespace Case_3 {
int Depth[100010];
int Sub_cnt[100010];
int Tree_up[100010][20];
int D_to_Y[100010];
vector <int> Child[100010];
vector <int> DList[100010];
int dfn_st[100010], dfn_en[100010], dfn_cs;
void dfs(int x) {
dfn_st[x] = ++dfn_cs;
Sub_cnt[x] = 1;
for(int e : Child[x]) {
Depth[e] = Depth[x] + 1;
Tree_up[e][0] = x;
for(int i=1;i<20;i++) {
Tree_up[e][i] = Tree_up[ Tree_up[e][i-1] ][i-1];
}
dfs(e);
Sub_cnt[x] += Sub_cnt[e];
}
dfn_en[x] = dfn_cs;
}
int Tree_climb(int x, int a) {
rep(i, 20) if(1<<i & a) x = Tree_up[x][i];
return x;
}
vector <pii> QList[100010];
vector <int> DV[100010];
int BIT[100010];
void update_bit(int x, int v) {
for(int i=x;i<100010;i+=(i&-i)) BIT[i] += v;
}
int read_bit(int l, int r) {
int res = 0;
for(int i=r;i;i-=(i&-i)) res += BIT[i];
for(int i=l-1;i;i-=(i&-i)) res -= BIT[i];
return res;
}
void Do() {
int cnt = 0;
for(int e : VList) {
for(int f : Rev_A[e]) {
if(e == Cycle[0] && f == Path[0]);
else Child[e].pb(f), ++cnt;
}
}
dfs(Path[0]);
	
int max_depth = 0;
for(int e : VList) max_depth = max(max_depth, Depth[e]);
auto add_event = [&](int y, int d) {
DList[y].pb(d);
};
for(int D = 0; D <= max_depth; D++) {
int len = D + 1;
int idx = ((Path_len - 1 - K) % len + len) % len;
D_to_Y[D] = idx;
for(int j=idx;j<=max_depth;j+=len) add_event(j, D);
}
		
for(int i=0;i<=max_depth;i++) {
sort(all(DList[i]));
}
	
int In_path[100010] = {};
for(int e : Path) In_path[e] = 1;
	
auto add_ans = [&](int x, int d, ll val) {
if(In_path[x] == 0) ans[x] += val;
};
for(int e : VList) {
int expected_d = Depth[e];
for(int y = D_to_Y[expected_d]; y < Depth[e]; y += expected_d + 1) {
int ue = Tree_climb(e, Depth[e] - y);
add_ans(ue, expected_d, Sub_cnt[e]);
}
}
for(int e : VList) {
int expected_d = Depth[e] - Num_Path[e] - 1;
if(expected_d == -1 || D_to_Y[expected_d] > Depth[e]) continue;
int start_y = D_to_Y[expected_d];
int mx_x = (Depth[e] - start_y - 1) / (expected_d + 1);
for(int x = mx_x; x >= 0; x--) {
int y = x * (expected_d + 1) + start_y;
int ue = Tree_climb(e, Depth[e] - y);
if(In_path[ue]) break;
add_ans(ue, expected_d, -Sub_cnt[e]);
}
}
for(int e : VList) if(In_path[e] == 0) {
int expected_d = Depth[e];
int depth_e = Depth[e];
int v = (int)(upper_bound(all(DList[depth_e]), expected_d) - DList[depth_e].begin());
ans[e] += (ll) v * Sub_cnt[e];
}
for(int e : VList) if(In_path[e] == 0) {
int expected_d = Depth[e] - Num_Path[e] - 1;
int depth_e = Depth[e];
int v = (int)(upper_bound(all(DList[depth_e]), expected_d) - DList[depth_e].begin());
ans[e] -= (ll) v * Sub_cnt[e];
}
rep(i, Path_len) {
for(int d : DList[i]) {
int lv = max(i, d);
int rv = min(i + d, max_depth);
QList[rv].pb(pii(Path[i], 1));
if(lv) QList[lv-1].pb(pii(Path[i], -1));
}
}
for(int e : VList) DV[Depth[e]].pb(e);
for(int i=0;i<=max_depth;i++) {
for(int e : DV[i]) {
update_bit(dfn_st[e], 1);
}
for(pii q : QList[i]) {
int r = read_bit(dfn_st[q.Fi], dfn_en[q.Fi]);
ans[q.Fi] += r * q.Se;
}
}
}
}

int main() {
scanf("%d%lld", &N, &K);
for(int i=1;i<=N;i++) scanf("%d", A + i);
for(int i=1;i<=N;i++) Rev_A[A[i]].pb(i);
for(int i=1;i<=N;i++) pp[i] = i;
for(int i=1;i<=N;i++) pp[Find(i)] = Find(A[i]);
int deg[100010] = {};
for(int i=1;i<=N;i++) deg[A[i]]++;
vector<int> q;
for(int i=1;i<=N;i++) if(deg[i] == 0) q.pb(i);
rep(i, szz(q)) {
int t = q[i];
deg[A[t]]--;
if(deg[A[t]] == 0) q.pb(A[t]);
}
for(int i=1;i<=N;i++) chk_cycle[i] = deg[i];
int temp = 1;
while(deg[temp] == 0) {
Tail.pb(temp);
temp = A[temp];
}
Cycle.pb(temp);
for(int t=A[temp];t!=temp;t=A[t]) Cycle.pb(t);
int expected_ans = Cycle[ (K - szz(Tail)) % szz(Cycle) ];
ans[expected_ans] += N * (ll) (N - szz(Cycle) - szz(Tail));
for(int i=1;i<=N;i++) if(deg[i] == 1 && Find(i) != Find(1) && color[i] == 0) {
Case_1::Do(i, szz(Tail) + szz(Cycle));
}
Case_2::Do();
Case_3::Do();
for(int i=1;i<=N;i++) printf("%lld\n", ans[i]);
return 0;
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:356:6: 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:357:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 for(int i=1;i<=N;i++) scanf("%d", A + i);
                       ~~~~~^~~~~~~~~~~~~

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