//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 100111;
int n, a[maxn], L;
ll K;
int go[60][maxn];
ll ans[maxn];
vector<int> route;
int rid[maxn], T;
bool on_route[maxn];
ll lz[60][maxn];
void add(int x, ll m, ll v)
{
for (int i=59; i>=0; i--)
{
if (m>=(1ll<<i))
{
lz[i][x] += v;
m -= 1<<i;
x = go[i][x];
}
}
}
void add_lazy(int x, ll l, ll r, ll v)
{
// cerr<<"add_lazy:"<<x<<" "<<l<<","<<r<<" "<<v<<endl;
add(x, r, v);
add(x, l-1, -v);
}
void dfs(int x, ll l)
{
if (!l||on_route[x]) return;
on_route[x] = true;
rid[x] = route.size();
route.PB(x);
dfs(a[x], l-1);
}
void after_work()
{
for (int i=59; i>=0; i--)
{
for (int x=1; x<=n; x++)
{
if (i>0)
{
lz[i-1][x] += lz[i][x];
lz[i-1][go[i-1][x]] += lz[i][x];
}
else
{
ans[x] += lz[0][x];
}
}
}
}
int main()
{
scanf("%d%lld", &n, &K);
for (int i=1; i<=n; i++) scanf("%d", &a[i]), go[0][i] = a[i];
dfs(1, K);
for (int i=1; i<60; i++) for (int j=1; j<=n; j++) go[i][j] = go[i-1][go[i-1][j]];
T = 1;
for (int i=0; i<60; i++) if ((K>>i)&1) T = go[i][T];
L = route.size();
//a is not in route
{
int cnt = 0;
for (int i=1; i<=n; i++) cnt += !on_route[i];
ans[T] += 1ll*cnt*n;
}
// for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
//a is in route, b is not in route
{
for (int i=1; i<=n; i++)
{
if (!on_route[i])
{
add_lazy(i, K-L, K-1, 1);
}
}
}
//a is in route, b is in route
{
for (int i=1; i<=L; i++)
{
int c = K%i;
int lst = i-2;
for (int k=0; k*i+c<L; k++)
{
int r = min(L-1, k*i+i-1+c);
ans[route[k*i+c]] += r-lst;
lst = r;
}
/*
for (int j=i-1; j<L; j++)
{
ans[route[((j-c)/i)*i+c]]++;
}
*/
}
for (int i=0; i<L; i++)
{
int c = K%(L-i);
ans[route[c]] += max(0, L-(c+i+1));
ans[route[c+i]] += L-i-1-max(0, L-(c+i+1));
}
}
// for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
after_work();
for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
return 0;
}
/*
5 7
5 1 4 3 2
*/
Compilation message
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:64: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:65:45: 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]), go[0][i] = a[i];
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
869 ms |
72740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
