| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52220 |
2018-06-25T05:14:52 Z |
koosaga(#1343) |
Space Pirate (JOI14_space_pirate) |
C++11 |
|
502 ms |
49520 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
lint k;
int n, a[100005];
int par[60][100005];
vector<int> gph[100005];
int anc(int x, lint k){
for(int i=0; k; i++){
if((k >> i) & 1){
k ^= (1ll << i);
x = par[i][x];
}
}
return x;
}
lint ans[100005];
int cnt[100005], up[100005], lev[100005], cmp[100005];
int din[100005], dout[100005], piv;
bool sub(int s, int t){
return din[s] <= din[t] && dout[t] <= dout[s];
}
void dfs(int x, int p){
din[x] = piv++;
for(auto &i : gph[x]){
if(i != p && cnt[i] != 2){
lev[i] = lev[x] + 1;
cmp[i] = cmp[x];
dfs(i, x);
}
}
dout[x] = piv;
}
vector<pi> qry[100005];
int deg[100005], levl[100005], cmpl[100005];
int cn[100005], cg[100005], csz[100005], ch[100005], rev[100005], piv2, piv3;
lint dx1[100005], dx2[100005];
void dfs2(int x, int p){
for(auto &i : gph[x]){
if(i != p && !deg[i]){
levl[i] = levl[x] + 1;
cmpl[i] = cmpl[x];
dfs2(i, x);
}
}
}
void dfs3(int x, int p){
for(auto &i : gph[x]){
if(i != p && !deg[i]){
dfs3(i, x);
dx1[x] += dx1[i];
}
}
}
void clear_line(){
queue<int> que;
for(int i=1; i<=n; i++){
if(!deg[i]) que.push(i);
}
while(!que.empty()){
int x = que.front();
que.pop();
deg[a[x]]--;
if(deg[a[x]] == 0) que.push(a[x]);
}
for(int i=1; i<=n; i++){
if(deg[i]){
cmpl[i] = i;
dfs2(i, -1);
}
}
for(int i=1; i<=n; i++){
if(deg[i] && !cn[i]){
piv2++;
ch[piv2] = i;
for(int j=i; !cn[j]; j=a[j]){
cg[j] = piv2;
cn[j] = ++piv3;
csz[piv2]++;
}
}
}
for(int i=1; i<=n; i++){
rev[cn[i]] = i;
}
for(int i=1; i<=n; i++){
for(auto &j : qry[i]){
int cnt = j.first;
int len = j.second;
if(len > levl[i]){
dx1[i] += cnt;
dx1[cmpl[i]] -= cnt;
len -= levl[i];
int compidx = cg[cmpl[i]];
int compnum = cn[cmpl[i]];
int compsize = csz[compidx];
int comphead = ch[compidx];
if(compnum + len - 1 >= compsize + cn[comphead]){
dx2[compnum] += cnt;
dx2[cn[comphead] + compsize] -= cnt;
len -= compsize + cn[comphead] - compnum;
dx2[cn[comphead]] += 1ll * cnt * (len / compsize);
dx2[cn[comphead] + compsize] -= 1ll * cnt * (len / compsize);
len %= compsize;
dx2[cn[comphead]] += cnt;
dx2[cn[comphead] + len] -= cnt;
}
else{
dx2[compnum] += cnt;
dx2[compnum + len] -= cnt;
}
}
else{
dx1[i] += cnt;
dx1[anc(i, len)] -= cnt;
}
}
}
for(int i=1; i<=piv3; i++){
dx2[i] += dx2[i-1];
if(deg[i]) dfs3(i, -1);
}
for(int i=1; i<=n; i++){
if(deg[i]) ans[i] += dx2[cn[i]];
ans[i] += dx1[i];
}
}
void update(int s, lint l1, lint l2, int x){
s = anc(s, l1);
qry[s].push_back(pi(x, l2 - l1 + 1));
}
int oneanc[100005];
void dfs4(int x, int p){
for(auto &i : gph[x]){
if(cnt[i] != 1 && i != p){
oneanc[i] = oneanc[x];
dfs4(i, x);
}
}
}
void mod_gazua(int v, int os, int s, int e){
assert(os >= 0);
for(int i=s; i<=e; i++){
ans[anc(v, (k + os) % i)]++;
}
}
int main(){
scanf("%d %lld",&n,&k);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
deg[a[i]]++;
gph[a[i]].push_back(i);
par[0][i] = a[i];
}
for(int i=1; i<60; i++){
for(int j=1; j<=n; j++){
par[i][j] = par[i-1][par[i-1][j]];
}
}
int idx = 0, st = 1e9, ed = -1e9;
for(int p=1; cnt[p]<2; p=a[p]) cnt[p]++;
for(int p=1; !up[p]; p=a[p]) up[p] = ++idx;
for(int i=1; i<=n; i++){
if(cnt[i] == 2){
st = min(st, up[i]);
ed = max(ed, up[i]);
cmp[i] = i;
dfs(i, -1);
}
if(cnt[i] == 1){
oneanc[i] = i;
dfs4(i, -1);
}
}
ans[anc(1, k)] += n * (max(0ll, ed - k) + count(cnt + 1, cnt + n + 1, 0));
for(int i=1; i<=n; i++){
if(max(k - ed, 0ll) <= k - st && cmp[i] == 0) update(i, max(k - ed, 0ll), k - st, 1);
if(max(k - st + 1, 0ll) <= k - 1) update(i, max(k - st + 1, 0ll), k - 1, 1);
if(up[i] == st && up[i] <= k){
for(int j=1; j<=ed-st+1; j++){
int iter = min(k - up[i] + 1, ed - st + 1ll);
lint cnt = ed - st + 2 - j + k - up[i];
for(int it=0; ; it++){
int p = (k - up[i]) % j - j + 1 + it * j;
int q = (k - up[i]) % j + it * j;
if(p >= iter) break;
int nxt = anc(i, cnt - ((k - up[i] - q) / j) * j);
ans[nxt] += min(q, iter - 1) - max(0, p) + 1;
}
}
}
if(oneanc[i] > 0){
lint ved = k - up[oneanc[i]];
lint vst = k - st + 1;
vst = max(vst, 0ll);
if(vst <= ved) update(i, vst, ved, -1);
int sz = (int)min(1ll * st - up[oneanc[i]], k - up[oneanc[i]] + 1);
int c = lev[i] - lev[oneanc[i]];
lint u = - up[oneanc[i]] + 1 + lev[i] - lev[oneanc[i]];
mod_gazua(i, u, c + 1, c + sz); // TODO 1
}
}
for(int i=1; i<=n; i++){
if(cmp[i] && cnt[i] != 2){
int uci = up[cmp[i]];
int vst = st, ved = min(1ll * ed, k);
if(vst < min(uci, ved + 1)){
int md = ed - st + 1 - uci + 1 + lev[i];
mod_gazua(i, md, vst + md, min(uci, ved + 1) - 1 + md); // TODO 2
}
if(max(vst, uci) <= ved){
int md = lev[i] + 1 - uci;
mod_gazua(i, md, max(uci, vst) + md, ved + md); // TODO 3
}
}
}
clear_line();
for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}
Compilation message
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:165: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:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
502 ms |
47636 KB |
Output is correct |
| 2 |
Correct |
368 ms |
47636 KB |
Output is correct |
| 3 |
Correct |
401 ms |
47636 KB |
Output is correct |
| 4 |
Correct |
374 ms |
49124 KB |
Output is correct |
| 5 |
Correct |
358 ms |
49124 KB |
Output is correct |
| 6 |
Correct |
374 ms |
49520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
