oj.uz

Submission #113477

# Submission time Handle Problem Language Result Execution time Memory
113477 2019-05-25T21:43:43 Z cki86201 Space Pirate (JOI14_space_pirate) C++11
100 / 100
 825 ms 99056 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 17 ms 18944 KB Output is correct
3 Correct 16 ms 18816 KB Output is correct
4 Correct 17 ms 18944 KB Output is correct
5 Correct 18 ms 18944 KB Output is correct
6 Correct 17 ms 18944 KB Output is correct
7 Correct 17 ms 18908 KB Output is correct
8 Correct 17 ms 18816 KB Output is correct
9 Correct 17 ms 18944 KB Output is correct
10 Correct 17 ms 18944 KB Output is correct
11 Correct 18 ms 18816 KB Output is correct
12 Correct 17 ms 18944 KB Output is correct
13 Correct 18 ms 18944 KB Output is correct
14 Correct 18 ms 18944 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 17 ms 18944 KB Output is correct
3 Correct 16 ms 18816 KB Output is correct
4 Correct 17 ms 18944 KB Output is correct
5 Correct 18 ms 18944 KB Output is correct
6 Correct 17 ms 18944 KB Output is correct
7 Correct 17 ms 18908 KB Output is correct
8 Correct 17 ms 18816 KB Output is correct
9 Correct 17 ms 18944 KB Output is correct
10 Correct 17 ms 18944 KB Output is correct
11 Correct 18 ms 18816 KB Output is correct
12 Correct 17 ms 18944 KB Output is correct
13 Correct 18 ms 18944 KB Output is correct
14 Correct 18 ms 18944 KB Output is correct
15 Correct 20 ms 19840 KB Output is correct
16 Correct 20 ms 19584 KB Output is correct
17 Correct 21 ms 19832 KB Output is correct
18 Correct 25 ms 20984 KB Output is correct
19 Correct 23 ms 20224 KB Output is correct
20 Correct 25 ms 20476 KB Output is correct
21 Correct 24 ms 20864 KB Output is correct
22 Correct 24 ms 20352 KB Output is correct
23 Correct 25 ms 20728 KB Output is correct
24 Correct 22 ms 20224 KB Output is correct
25 Correct 20 ms 19584 KB Output is correct
26 Correct 25 ms 20856 KB Output is correct
27 Correct 23 ms 20088 KB Output is correct
28 Correct 23 ms 20096 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 30712 KB Output is correct
2 Correct 663 ms 99048 KB Output is correct
3 Correct 373 ms 69928 KB Output is correct
4 Correct 79 ms 28792 KB Output is correct
5 Correct 618 ms 99056 KB Output is correct
6 Correct 305 ms 68740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 17 ms 18944 KB Output is correct
3 Correct 16 ms 18816 KB Output is correct
4 Correct 17 ms 18944 KB Output is correct
5 Correct 18 ms 18944 KB Output is correct
6 Correct 17 ms 18944 KB Output is correct
7 Correct 17 ms 18908 KB Output is correct
8 Correct 17 ms 18816 KB Output is correct
9 Correct 17 ms 18944 KB Output is correct
10 Correct 17 ms 18944 KB Output is correct
11 Correct 18 ms 18816 KB Output is correct
12 Correct 17 ms 18944 KB Output is correct
13 Correct 18 ms 18944 KB Output is correct
14 Correct 18 ms 18944 KB Output is correct
15 Correct 20 ms 19840 KB Output is correct
16 Correct 20 ms 19584 KB Output is correct
17 Correct 21 ms 19832 KB Output is correct
18 Correct 25 ms 20984 KB Output is correct
19 Correct 23 ms 20224 KB Output is correct
20 Correct 25 ms 20476 KB Output is correct
21 Correct 24 ms 20864 KB Output is correct
22 Correct 24 ms 20352 KB Output is correct
23 Correct 25 ms 20728 KB Output is correct
24 Correct 22 ms 20224 KB Output is correct
25 Correct 20 ms 19584 KB Output is correct
26 Correct 25 ms 20856 KB Output is correct
27 Correct 23 ms 20088 KB Output is correct
28 Correct 23 ms 20096 KB Output is correct
29 Correct 92 ms 30712 KB Output is correct
30 Correct 663 ms 99048 KB Output is correct
31 Correct 373 ms 69928 KB Output is correct
32 Correct 79 ms 28792 KB Output is correct
33 Correct 618 ms 99056 KB Output is correct
34 Correct 305 ms 68740 KB Output is correct
35 Correct 181 ms 46016 KB Output is correct
36 Correct 212 ms 46004 KB Output is correct
37 Correct 128 ms 43508 KB Output is correct
38 Correct 689 ms 93900 KB Output is correct
39 Correct 349 ms 69996 KB Output is correct
40 Correct 683 ms 82748 KB Output is correct
41 Correct 750 ms 98084 KB Output is correct
42 Correct 522 ms 72368 KB Output is correct
43 Correct 539 ms 88260 KB Output is correct
44 Correct 365 ms 68848 KB Output is correct
45 Correct 76 ms 24432 KB Output is correct
46 Correct 825 ms 93712 KB Output is correct
47 Correct 294 ms 64304 KB Output is correct
48 Correct 333 ms 65260 KB Output is correct