Submission #252319

#TimeUsernameProblemLanguageResultExecution timeMemory
252319frodakcinSpace Pirate (JOI14_space_pirate)C++11
47 / 100
304 ms43380 KiB
#include <cstdio> #include <cassert> #include <cstring> #include <vector> #include <algorithm> #include <functional> using ll = long long; const int MN = 101000; int N, a[MN], X[MN], Y[MN], L, _map[MN*2], *map=_map+MN, p[MN][17], s[MN]; ll K, f[MN], psum[MN]; bool vis[MN]; std::vector<int> b[MN], path, invmap[MN*2], invmap2[MN*2]; void dfs(int n) { for(int i=0;p[n][i]&&p[p[n][i]][i];++i) p[n][i+1]=p[p[n][i]][i]; vis[n]=1; s[n] = 1; for(auto x:b[n]) if(vis[x]) { assert(x==path.front()); L=X[n]; assert(path[L]==n); } else { if(!~X[x]) X[x]=X[n]; Y[x]=Y[n]+1; p[x][0]=n, dfs(x); s[n]+=s[x]; } //printf("%d: [X: %d, Y: %d, s: %d]\n", n, X[n], Y[n]); } void case2(int n, int gL) { std::vector<int> q(0); for(;;n=a[n]) { if(vis[n]) break; q.push_back(n); vis[n]=1; } std::reverse(q.begin(), q.end()); assert(a[q.front()] == n); int L=0; for(;q[L]!=n;++L); ++L; ll cv=0; std::vector<int> p(L,0); int KmL = K%L; auto upd = [&](int depth)//reaches zero after [depth] steps { //end up at start_node - K //(depth + v + 1) - K // for all v = [0,gL) // inc(depth+1-K, depth+gL+1-K); inc-exc int l=(depth+1-KmL+L)%L; int r=l+gL; if(r-l>L) { int d = (r-l)/L; r-=d*L; cv+=d; } assert(r<2*L); if(r<L) ++p[l], --p[r]; else ++cv, --p[r-L], ++p[l]; }; std::function<void(int, int)> dfs=[&](int n, int d) { upd(d); vis[n]=1; for(auto x:b[n]) if(!vis[x]) dfs(x, d+1); }; for(int i=0;i<q.size();++i) dfs(q[i], i); for(int i=0;i<L;++i) f[q[i]] += cv += p[i];//impact } int mup(int n, int d) { assert(d<=Y[n]);//minor assert for(int i=0;d;++i, d>>=1) if(d&1) n=p[n][i]; assert(n);//minor assert return n; } void dfs1(int n, int offset)//case 3A { vis[n]=1; for(auto x:b[n]) if(!vis[x]) dfs1(x, offset); int d=Y[n]; ll l = K-d-1-offset, r = K-d-1; psum[0]-=l/L, ++psum[l%L]; psum[0]+=r/L, --psum[r%L]; } void dfs2(int n)//case 3B { vis[n]=1; for(auto x:b[n]) if(!vis[x]) dfs2(x); //now, we do the black magic int D, E; //top (inclusive) D = Y[n]-(X[n]+1); E = map[D]; assert(E>=D+1 || Y[n]>=E); assert(Y[n]>=D); //true if(E<Y[n]) { int t=mup(n, Y[n]-E); if(D>=0) f[t]+=s[n];// Upper Normal (+E) } else { E-=D+1; if(D>=0) f[path[E]]+=s[n];// Upper Boundary (+E') } //bottom (exclusive) D = Y[n]-L; E = map[D]; assert(E>=D+1 || Y[n]>=E); assert(Y[n]>=D); //true if(E<Y[n]) { int t=mup(n, Y[n]-E); f[t]-=s[n];// Bottom Normal (-E) } else { E-=D+1; f[path[E]]-=s[n];// Bottom Boundary (-E') } //self : D in (Y-L, Y-X) (exc, exc) int x=std::distance(std::upper_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-L), std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-X[n])); f[n]+=(ll)x*s[n];// Boundary Normal (+E) psum[Y[n]]+=s[n]; } void dfs3(int n) { vis[n]=1; for(auto x:b[n]) if(!vis[x]) dfs3(x); //black magic part 2 int D, E; //top(inc) D = Y[n]; if(D>0)//aka D exists { E = Y[n]-(Y[n]-map[D]+D+1)%(D+1); f[mup(n, Y[n]-E)] += s[n]; // Top Normal } //bot(exc) D = Y[n]-X[n]-1; if(D>0)//again, D exists { E = (Y[n]-1)-(Y[n]-1-map[D]+D+1)%(D+1); f[mup(n, Y[n]-E)] -= s[n]; // Bot Normal } //self: [Y[n]-X[n], Y[n]) (inc, exc). If you map to yourself, then it's already accounted for int x=std::distance(std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n]-X[n]), std::lower_bound(invmap[Y[n]].begin(), invmap[Y[n]].end(), Y[n])); f[n]+=(ll)x*s[n]; psum[Y[n]]+=s[n]; } int main() { scanf("%d%lld", &N, &K); for(int i=1;i<=N;++i) scanf("%d", a+i), b[a[i]].push_back(i); for(int n=1;;n=a[n]) { if(vis[n]) break; vis[n]=1; path.push_back(n); } memset(vis+1, 0, N*sizeof*vis); memset(X+1, -1, N*sizeof*X); std::reverse(path.begin(), path.end());//path[0] = root of tree for(int i=0;i<path.size();++i) X[path[i]]=i; dfs(path.front()); ++L;//# of nodes, not index //printf("PATH:"); for(int i=0;i<path.size();++i) printf(" %d", path[i]); printf("\n"); f[path[L-(K-path.size())%L-1]] += (ll)N*(N-path.size());//other -> ALL //at this point, every vis[(main)] = true //path -> non-main (Case 2) for(int i=1;i<=N;++i) if(!vis[i]) case2(i, path.size()); //printf("CHECK 2: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]); //memset(f+1, 0, N*sizeof*f);//TEMPORARY FOR TESTING //CHECK #1 SEEMS TO WORK //non-cyc -> non-subtree (case 3A) if(L<path.size()) { memset(vis+1, 0, N*sizeof*vis); for(auto x:path) vis[x]=1; for(int i=0;i+1<path.size();++i) dfs1(path[i], path.size()-std::max(L, i+1)); ll cv=0; for(int i=0;i<L;++i) f[path[L-i-1]]+=cv+=psum[i]; memset(psum, 0, L*sizeof*psum); } //printf("CHECK 3A: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]); //memset(f+1, 0, N*sizeof*f);//TEMPORARY FOR TESTING //cyc -> non-subtree (case 3B) for(int i=-L;i<=N;++i)//technically 1-L is the true bound, but whatever. should be identical { int nL=L+i+1; map[i]=nL-(K-path.size()+L)%nL-1, invmap[map[i]].push_back(i);//L'=L+D+1 if(map[i]>i-1)//technically >=, but invmap2[0] is never used... invmap2[map[i]-i-1].push_back(i); //printf("MAP: %d -> %d\n", i, map[i]); } memset(vis+1, 0, N*sizeof*vis); for(auto x:path)vis[x]=1; /* For each triangle D: - Definition: E = expected depth = par at depth map[D] - Definition: E'= special path node = path[map[D]-D-1] - Upper: +E' if boundary deeper, else +E. Equality: +E' - Bound: -E'+E if boundary exists in triangle, inclusive on both top&bot - Lower: -E' if boundary deeper, else -E. Equality: -E' */ if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]-=s[path[L]]; for(int i=0;i<L;++i) { dfs2(path[i]); for(auto D:invmap2[i]) { //cutoff point = true E = i+D+1 //X-value must be strictly less than E-D = strictly less than i+1 = less than eq to i int E = i+D+1; //check to see if removing this is actually warranted assert(0<=E);//actually I daresay 0 < E is assertable. check line 206 if(0<=E && E<D+L)//E is (inclusively) in triangle of D. (D+1 or D?) <= E is guaraunteed, so E is definitely low enough. Just have to check if it's too low f[path[i]] -= psum[E];//-E' //Very interesting dynamic happened in above line. path[E-D-1]=target => implying sum of boundary = (sum s[n], provided [Y[n]==E && X[n]<=E-D-1]) //X[n]<=E-D-1, because triangle D, Y[n]=E => path[E-D] is valid A node, so (X[n] < X[path[E-D]] = E-D) } } for(int i=-L;i<0;++i) { assert(0 <= map[i]-i-1 && map[i]-i-1 < L); f[path[map[i]-i-1]]+=s[path[0]];//Upper Special (+E') } if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]+=s[path[L]]; //printf("CHECK 3B: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]); //memset(f+1, 0, N*sizeof*f);//TEMP RESET //path -> subtree (case 3C) memset(psum, 0, N*sizeof*psum); for(int i=0;i<=N;++i) invmap[i].clear(); for(int i=1;i<=N;++i)// 0 = node -> itself. also N is impossible.. { map[i]=i-(K-path.size())%(i+1); //printf("MAP %d -> %d\n", i, map[i]); for(int j=map[i];j<=N;j+=i+1) invmap[j].push_back(i); } memset(vis+1, 0, N*sizeof*vis); for(auto x:path) vis[x]=1; for(int i=path.size()-1;i>=0;--i) { for(auto x:invmap[i]) if(i+x+1<N) f[path[i]] -= psum[i+x+1]; dfs3(path[i]); } for(auto x:path) ++f[x]; //printf("CHECK 3C: "); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]); for(int i=1;i<=N;++i) printf("%lld%c", f[i], " \n"[i==N]); return 0; }

Compilation message (stderr)

space_pirate.cpp: In function 'void case2(int, int)':
space_pirate.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<q.size();++i) dfs(q[i], i);
              ~^~~~~~~~~
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:193:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path.size();++i)
              ~^~~~~~~~~~~~
space_pirate.cpp:213:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size())
     ~^~~~~~~~~~~~
space_pirate.cpp:217:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<path.size();++i)
               ~~~^~~~~~~~~~~~
space_pirate.cpp:247:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]-=s[path[L]];
     ~^~~~~~~~~~~~
space_pirate.cpp:269:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(L<path.size()) for(int i=0;i<L;++i) s[path[i]]+=s[path[L]];
     ~^~~~~~~~~~~~
space_pirate.cpp:181: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:182:40: 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), b[a[i]].push_back(i);
                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...