Submission #136631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136631	2019-07-25T23:01:16 Z	Benq	Space Pirate (JOI14_space_pirate)	C++14	80 / 100	2000 ms	93224 KB

space_pirate

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
 
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 100005;
const ld PI = 4*atan((ld)1);
 
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
 
namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
 
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) { 
        re(first); re(rest...); 
    }
 
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}
 
using namespace input;
 
namespace output {
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T, size_t SZ> void pr(const array<T,SZ>& x);
    template<class T> void pr(const vector<T>& x);
    template<class T> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    template<class T> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
        pr(first); pr(rest...); 
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void prContain(const T& x) {
        pr("{");
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
        pr("}");
    }
    template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    template<class T> void pr(const vector<T>& x) { prContain(x); }
    template<class T> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
    
    void ps() { pr("\n"); }
    template<class Arg> void ps(const Arg& first) { 
        pr(first); ps(); // no space at end of line
    }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { 
        pr(first," "); ps(rest...); // print w/ spaces
    }
}
 
using namespace output;
 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;

int N,A[MX]; // ind[MX],ori;
ll K, ans[MX];
 
vector<vi> cyc;
array<int,3> CYC[MX];
int vis[MX];
 
int par(int a, ll b) {
	assert(b >= CYC[a][2]);
	b -= CYC[a][2];
	int ind = (CYC[a][1]+b)%sz(cyc[CYC[a][0]]);
	return cyc[CYC[a][0]][ind];
}
 
void dfs(int a, int b) {
	if (vis[a]) {
		if (vis[a] != b) return;
		array<int,3> lst = {sz(cyc),0,0}; cyc.pb({});
		while (CYC[a][0] == -1) {
			CYC[a] = lst; cyc.back().pb(a);
			lst[1] ++; a = A[a];
		}
		return;
	}
	vis[a] = b; dfs(A[a],b);
	if (CYC[a][0] == -1) CYC[a] = {CYC[A[a]][0],CYC[A[a]][1],CYC[A[a]][2]+1};
}
 
vi adj[MX];
int dist[MX],ind[MX];
int special;
vl cum[MX];
vi path;
 
void genInd(int x) {
	trav(t,adj[x]) if (ind[t] == MOD) {
		ind[t] = ind[x];
		genInd(t);
	}
}
 
void ad(int ind, ll L, ll R) {
	// FOR(i,L,R+1) ans[cyc[ind][i%sz(cyc[ind])]] ++;
	ll tot = (R-L+1)/sz(cyc[ind]);
	cum[ind][0] += tot; R -= tot*sz(cyc[ind]);
	ll z = L/sz(cyc[ind]); L -= z*sz(cyc[ind]), R -= z*sz(cyc[ind]);
	cum[ind][L] ++;
	if (R+1 < sz(cyc[ind])) cum[ind][R+1] --;
	else cum[ind][0] ++, cum[ind][R+1-sz(cyc[ind])] --;
}
 
void init() {
    setIO(); re(N,K); 
    FOR(i,1,N+1) {
    	re(A[i]);
    	adj[A[i]].pb(i);
    	CYC[i] = {-1,-1,-1}; // cycle, position, dist
    }
    FOR(i,1,N+1) if (!vis[i]) dfs(i,i);
    FOR(i,1,N+1) dist[i] = -1, ind[i] = MOD;
    
    int cur = 1, lst = 0;
    while (dist[cur] == -1) {
    	dist[cur] = ind[cur] = lst++;
    	if (CYC[cur][2] == 0) ind[cur] = CYC[1][2];
    	path.pb(cur);
    	cur = A[cur];
    }
    F0R(i,sz(path)) genInd(path[i]);
    ans[par(1,K)] += (ll)N*(N-sz(path));
    F0R(i,sz(cyc)) cum[i].rsz(sz(cyc[i]));
    // FOR(i,1,N+1) ps("HA",i,ind[i]);
    FOR(i,1,N+1) {
    	int lo = 1, hi = min(sz(path),ind[i]); 
    	lo += CYC[i][2], hi += CYC[i][2];
    	// ps("??",i,lo,hi);
    	ad(CYC[i][0],CYC[i][1]+K-hi,CYC[i][1]+K-lo);
    }
    F0R(i,sz(cyc)) {
    	F0R(j,sz(cyc[i])) {
    		if (j) cum[i][j] += cum[i][j-1];
    		ans[cyc[i][j]] += cum[i][j];
    	}
    }
}
 
vi v;
int dis[MX], disPath[MX];
 
void rdfs(int x) {
	v.pb(x); 
	int rem = (K-dist[special])%sz(v);
	if (rem == 0) ans[v[rem]] ++;
	else ans[v[sz(v)-rem]] ++;
	trav(t,adj[x]) if (t != special) rdfs(t);
	v.pop_back();
}
 
void process() {
	// ps("HUH",special,dist[special]); exit(0);
	rdfs(special);
	// FOR(i,1,N+1) if (lst[i] != special) ans[par(i,K-dist[special]-1)] ++;
}
 
vi todo[2*MX];

void genDis(int x) {
	trav(t,adj[x]) if (t != path.back()) {
		dis[t] = dis[x]+1;
		if (dist[t] == -1) disPath[t] = disPath[x]+1;
		genDis(t);
	}
}
 
template <class T, int ...Ns> struct BIT {
    T val = 0;
    void upd(T v) { val += v; }
    T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
    BIT<T,Ns...> bit[N + 1];
    template<typename... Args> void upd(int pos, Args... args) {
        for (; pos <= N; pos += (pos&-pos)) bit[pos].upd(args...);
    }
    template<typename... Args> T sum(int r, Args... args) {
        T res = 0; for (; r; r -= (r&-r)) res += bit[r].query(args...); 
        return res;
    }
    template<typename... Args> T query(int l, int r, Args... args) {
    	ckmax(l,1); ckmin(r,N);
    	if (l > r) return 0;
        return sum(r,args...)-sum(l-1,args...);
    }
}; // BIT<int,10,10> gives a 2D BIT

BIT<int,MX> B, B2, B3, B4;
int cycLen;

void ans1(int x) {
	// ps("HA",x,dis[x]);
	trav(len,todo[dis[x]]) {
		int l = max(1,dis[x]-len+1)+len-1;
		int r = dis[x]-disPath[x]+len-1;
		ans[x] -= B.query(l,r);
	}
	B.upd(dis[x],1); 
	trav(t,adj[x]) if (t != path.back()) ans1(t);
	trav(len,todo[dis[x]]) {
		int l = max(1,dis[x]-len+1)+len-1;
		int r = dis[x]-disPath[x]+len-1;
		// ps("WUT",dis[x],len,l,r,B.query(l,r));
		ans[x] += B.query(l,r);
	}
	// cycLen to cycLen+len-1
	// ps("FINISH",x,dis[x],ans[x]);
}

vi weird[MX], WEIRD[MX];
vi ins[2*MX], del[2*MX], INS[2*MX], DEL[2*MX];

void ans2(int x) {
	if (dist[x] == -1) {
		trav(len,todo[dis[x]+cycLen]) {
			int l = dis[x]-disPath[x]+1, r = cycLen;
			l += len-1-cycLen, r += len-1-cycLen;
			ans[x] -= B2.query(l,r);
		}
	} else {
		trav(t,todo[dis[x]+cycLen]) weird[t].pb(x);
		if (dis[x] <= cycLen) trav(t,todo[dis[x]]) WEIRD[t].pb(x);
	}
	int a = dis[x]-disPath[x], b = disPath[x];
	int l = a+b+1, r = b+cycLen;
	if (l <= r) ins[l].pb(a), del[r+1].pb(a);
	INS[1].pb(a+b), DEL[b+cycLen+1].pb(a+b);
	// len <= , a+b <= len-1
	// [a+b+1,b+cycLen]
	// bad when len > b+cycLen, len <= a+b
	B2.upd(dis[x],1);
	trav(t,adj[x]) if (t != path.back()) ans2(t);
	if (dist[x] == -1) {
		trav(len,todo[dis[x]+cycLen]) {
			int l = dis[x]-disPath[x]+1, r = cycLen;
			l += len-1-cycLen, r += len-1-cycLen;
			ans[x] += B2.query(l,r);
		}
	} 
}

int main() {
	init();
	//ps(path);
	FOR(i,1,N+1) dis[i] = -1;
	dis[path.back()] = 1;
	genDis(path.back());
	FOR(len,1,N+1) {
		int rem = (dis[1]-K)%len; if (rem <= 0) rem += len;
		for (int i = rem; i <= 2*N; i += len) todo[i].pb(len);
	}
	cycLen = dis[A[path.back()]];
	ans1(path.back());
	ans2(path.back());
	FOR(len,1,N+1) {
		trav(t,ins[len]) B3.upd(t,1);
		trav(t,del[len]) B3.upd(t,-1);
		trav(t,INS[len]) B4.upd(t,1);
		trav(t,DEL[len]) B4.upd(t,-1);
		trav(t,weird[len]) ans[t] += B3.query(dis[t],MOD);
		trav(t,WEIRD[len]) ans[t] += B4.query(1,len-1-cycLen+dis[t]);
	}
    FOR(i,1,N+1) ps(ans[i]);
    exit(0);
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?), set tle
    * do smth instead of nothing and stay organized
*/

Compilation message

space_pirate.cpp: In function 'void io::setIn(std::__cxx11::string)':
space_pirate.cpp:113:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
space_pirate.cpp: In function 'void io::setOut(std::__cxx11::string)':
space_pirate.cpp:114:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	33528 KB	Output is correct
2	Correct	38 ms	33400 KB	Output is correct
3	Correct	35 ms	33372 KB	Output is correct
4	Correct	35 ms	33400 KB	Output is correct
5	Correct	41 ms	33372 KB	Output is correct
6	Correct	41 ms	33400 KB	Output is correct
7	Correct	35 ms	33400 KB	Output is correct
8	Correct	36 ms	33400 KB	Output is correct
9	Correct	35 ms	33400 KB	Output is correct
10	Correct	35 ms	33400 KB	Output is correct
11	Correct	35 ms	33400 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33400 KB	Output is correct
14	Correct	36 ms	33400 KB	Output is correct

Subtask #2

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	33528 KB	Output is correct
2	Correct	38 ms	33400 KB	Output is correct
3	Correct	35 ms	33372 KB	Output is correct
4	Correct	35 ms	33400 KB	Output is correct
5	Correct	41 ms	33372 KB	Output is correct
6	Correct	41 ms	33400 KB	Output is correct
7	Correct	35 ms	33400 KB	Output is correct
8	Correct	36 ms	33400 KB	Output is correct
9	Correct	35 ms	33400 KB	Output is correct
10	Correct	35 ms	33400 KB	Output is correct
11	Correct	35 ms	33400 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33400 KB	Output is correct
14	Correct	36 ms	33400 KB	Output is correct
15	Correct	41 ms	34168 KB	Output is correct
16	Correct	48 ms	34080 KB	Output is correct
17	Correct	41 ms	34068 KB	Output is correct
18	Correct	46 ms	34936 KB	Output is correct
19	Correct	43 ms	34652 KB	Output is correct
20	Correct	45 ms	34680 KB	Output is correct
21	Correct	44 ms	34680 KB	Output is correct
22	Correct	43 ms	34552 KB	Output is correct
23	Correct	43 ms	34552 KB	Output is correct
24	Correct	42 ms	34364 KB	Output is correct
25	Correct	40 ms	34040 KB	Output is correct
26	Correct	46 ms	34936 KB	Output is correct
27	Correct	69 ms	34396 KB	Output is correct
28	Correct	81 ms	34428 KB	Output is correct

Subtask #3

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	402 ms	61180 KB	Output is correct
2	Correct	1165 ms	93224 KB	Output is correct
3	Correct	838 ms	77276 KB	Output is correct
4	Correct	367 ms	61412 KB	Output is correct
5	Correct	887 ms	93208 KB	Output is correct
6	Correct	615 ms	76688 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	33528 KB	Output is correct
2	Correct	38 ms	33400 KB	Output is correct
3	Correct	35 ms	33372 KB	Output is correct
4	Correct	35 ms	33400 KB	Output is correct
5	Correct	41 ms	33372 KB	Output is correct
6	Correct	41 ms	33400 KB	Output is correct
7	Correct	35 ms	33400 KB	Output is correct
8	Correct	36 ms	33400 KB	Output is correct
9	Correct	35 ms	33400 KB	Output is correct
10	Correct	35 ms	33400 KB	Output is correct
11	Correct	35 ms	33400 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33400 KB	Output is correct
14	Correct	36 ms	33400 KB	Output is correct
15	Correct	41 ms	34168 KB	Output is correct
16	Correct	48 ms	34080 KB	Output is correct
17	Correct	41 ms	34068 KB	Output is correct
18	Correct	46 ms	34936 KB	Output is correct
19	Correct	43 ms	34652 KB	Output is correct
20	Correct	45 ms	34680 KB	Output is correct
21	Correct	44 ms	34680 KB	Output is correct
22	Correct	43 ms	34552 KB	Output is correct
23	Correct	43 ms	34552 KB	Output is correct
24	Correct	42 ms	34364 KB	Output is correct
25	Correct	40 ms	34040 KB	Output is correct
26	Correct	46 ms	34936 KB	Output is correct
27	Correct	69 ms	34396 KB	Output is correct
28	Correct	81 ms	34428 KB	Output is correct
29	Correct	402 ms	61180 KB	Output is correct
30	Correct	1165 ms	93224 KB	Output is correct
31	Correct	838 ms	77276 KB	Output is correct
32	Correct	367 ms	61412 KB	Output is correct
33	Correct	887 ms	93208 KB	Output is correct
34	Correct	615 ms	76688 KB	Output is correct
35	Correct	465 ms	59768 KB	Output is correct
36	Correct	474 ms	60528 KB	Output is correct
37	Correct	410 ms	58812 KB	Output is correct
38	Correct	905 ms	90252 KB	Output is correct
39	Correct	700 ms	77404 KB	Output is correct
40	Correct	894 ms	87408 KB	Output is correct
41	Correct	1142 ms	92572 KB	Output is correct
42	Correct	942 ms	77252 KB	Output is correct
43	Correct	668 ms	77864 KB	Output is correct
44	Correct	682 ms	71404 KB	Output is correct
45	Correct	320 ms	58436 KB	Output is correct
46	Correct	817 ms	90432 KB	Output is correct
47	Execution timed out	2054 ms	68916 KB	Time limit exceeded
48	Halted	0 ms	0 KB	-