Submission #136641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136641	2019-07-25T23:55:53 Z	Benq	Space Pirate (JOI14_space_pirate)	C++14	100 / 100	1843 ms	94464 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;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); 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;
const int MX = 100005;
 
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])] --;
}

clock_t beg;

void init() {
	//setIn("04-13.txt");
	//setOut("zz.txt");
	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
    }
    beg = clock();
    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];
 
vi todo[2*MX];
int maxDis[MX];

void genDis(int x) {
	trav(t,adj[x]) if (t != path.back()) {
		maxDis[t] = dis[t] = dis[x]+1;
		if (dist[t] == -1) disPath[t] = disPath[x]+1;
		genDis(t);
		ckmax(maxDis[x],maxDis[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(len,dis[x]); if (l > maxDis[x]) break;
		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(len,dis[x]); if (l > maxDis[x]) break;
		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];
ll xo = 0;

int cnt = 0, zero = 0;

void ans2(int x) {
	// vi z;
	int ind = lb(all(todo[dis[x]+cycLen]),dis[x])-todo[dis[x]+cycLen].begin();
	if (dist[x] == -1) {
		// cnt += sz(todo[dis[x]+cycLen]);
		FOR(i,ind,sz(todo[dis[x]+cycLen])) {
			int len = todo[dis[x]+cycLen][i];
			int l = dis[x]-disPath[x]+1, r = len-1;
			l += len-1-cycLen;
			if (l > maxDis[x] || l > r) break;
			int b = B2.query(l,r);
			ans[x] -= b;
			// z.pb(b);
			cnt ++; 
		}
	} 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) {
		int co = 0;
		FOR(i,ind,sz(todo[dis[x]+cycLen])) {
			int len = todo[dis[x]+cycLen][i];
			int l = dis[x]-disPath[x]+1, r = len-1;
			l += len-1-cycLen;
			if (l > maxDis[x] || l > r) break;
			int b = B2.query(l,r);
			/*if (z[co] == b) {
				cerr << "?? " << l << " " << r << " " << maxDis[x] << " " << b << "\n";
				exit(0);
			}*/
			// zero += z[co] == b;
			co ++;
			ans[x] += b;
		}
	} 
}

int main() {
	init();
	//ps(path);
	FOR(i,1,N+1) dis[i] = -1;
	maxDis[path.back()] = 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()]];
    //cerr << "MID " << (double)(clock()-beg)/CLOCKS_PER_SEC << "\n";
	ans1(path.back());
    //cerr << "AFT " << (double)(clock()-beg)/CLOCKS_PER_SEC << "\n";
	ans2(path.back());
    //cerr << "HUH " << (double)(clock()-beg)/CLOCKS_PER_SEC << " " << cnt << " " << zero << "\n";
	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) {
    	xo ^= ans[i];
    	ps(ans[i]);
    }
    //cerr << "EN " << (double)(clock()-beg)/CLOCKS_PER_SEC << " " << xo << "\n";
}

Compilation message

space_pirate.cpp: In function 'void io::setIn(std::__cxx11::string)':
space_pirate.cpp:107: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:108: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	38 ms	33448 KB	Output is correct
2	Correct	41 ms	33400 KB	Output is correct
3	Correct	34 ms	33400 KB	Output is correct
4	Correct	41 ms	33400 KB	Output is correct
5	Correct	35 ms	33400 KB	Output is correct
6	Correct	34 ms	33400 KB	Output is correct
7	Correct	35 ms	33456 KB	Output is correct
8	Correct	35 ms	33396 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	33372 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33380 KB	Output is correct
14	Correct	35 ms	33400 KB	Output is correct

Subtask #2

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	33448 KB	Output is correct
2	Correct	41 ms	33400 KB	Output is correct
3	Correct	34 ms	33400 KB	Output is correct
4	Correct	41 ms	33400 KB	Output is correct
5	Correct	35 ms	33400 KB	Output is correct
6	Correct	34 ms	33400 KB	Output is correct
7	Correct	35 ms	33456 KB	Output is correct
8	Correct	35 ms	33396 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	33372 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33380 KB	Output is correct
14	Correct	35 ms	33400 KB	Output is correct
15	Correct	47 ms	34040 KB	Output is correct
16	Correct	39 ms	34040 KB	Output is correct
17	Correct	47 ms	34040 KB	Output is correct
18	Correct	53 ms	34936 KB	Output is correct
19	Correct	62 ms	34552 KB	Output is correct
20	Correct	85 ms	34680 KB	Output is correct
21	Correct	50 ms	34748 KB	Output is correct
22	Correct	43 ms	34552 KB	Output is correct
23	Correct	43 ms	34552 KB	Output is correct
24	Correct	41 ms	34424 KB	Output is correct
25	Correct	41 ms	34048 KB	Output is correct
26	Correct	45 ms	34940 KB	Output is correct
27	Correct	45 ms	34424 KB	Output is correct
28	Correct	43 ms	34424 KB	Output is correct

Subtask #3

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	348 ms	61048 KB	Output is correct
2	Correct	930 ms	94464 KB	Output is correct
3	Correct	728 ms	77748 KB	Output is correct
4	Correct	355 ms	61048 KB	Output is correct
5	Correct	921 ms	94404 KB	Output is correct
6	Correct	652 ms	77096 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	33448 KB	Output is correct
2	Correct	41 ms	33400 KB	Output is correct
3	Correct	34 ms	33400 KB	Output is correct
4	Correct	41 ms	33400 KB	Output is correct
5	Correct	35 ms	33400 KB	Output is correct
6	Correct	34 ms	33400 KB	Output is correct
7	Correct	35 ms	33456 KB	Output is correct
8	Correct	35 ms	33396 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	33372 KB	Output is correct
12	Correct	35 ms	33400 KB	Output is correct
13	Correct	35 ms	33380 KB	Output is correct
14	Correct	35 ms	33400 KB	Output is correct
15	Correct	47 ms	34040 KB	Output is correct
16	Correct	39 ms	34040 KB	Output is correct
17	Correct	47 ms	34040 KB	Output is correct
18	Correct	53 ms	34936 KB	Output is correct
19	Correct	62 ms	34552 KB	Output is correct
20	Correct	85 ms	34680 KB	Output is correct
21	Correct	50 ms	34748 KB	Output is correct
22	Correct	43 ms	34552 KB	Output is correct
23	Correct	43 ms	34552 KB	Output is correct
24	Correct	41 ms	34424 KB	Output is correct
25	Correct	41 ms	34048 KB	Output is correct
26	Correct	45 ms	34940 KB	Output is correct
27	Correct	45 ms	34424 KB	Output is correct
28	Correct	43 ms	34424 KB	Output is correct
29	Correct	348 ms	61048 KB	Output is correct
30	Correct	930 ms	94464 KB	Output is correct
31	Correct	728 ms	77748 KB	Output is correct
32	Correct	355 ms	61048 KB	Output is correct
33	Correct	921 ms	94404 KB	Output is correct
34	Correct	652 ms	77096 KB	Output is correct
35	Correct	447 ms	59732 KB	Output is correct
36	Correct	464 ms	60276 KB	Output is correct
37	Correct	398 ms	58724 KB	Output is correct
38	Correct	883 ms	91476 KB	Output is correct
39	Correct	630 ms	78008 KB	Output is correct
40	Correct	791 ms	88656 KB	Output is correct
41	Correct	962 ms	93864 KB	Output is correct
42	Correct	739 ms	77696 KB	Output is correct
43	Correct	713 ms	79076 KB	Output is correct
44	Correct	578 ms	72024 KB	Output is correct
45	Correct	342 ms	57720 KB	Output is correct
46	Correct	953 ms	91788 KB	Output is correct
47	Correct	1843 ms	71100 KB	Output is correct
48	Correct	1290 ms	74424 KB	Output is correct