oj.uz

Submission #136640

# Submission time Handle Problem Language Result Execution time Memory
136640 2019-07-25T23:46:27 Z Benq Space Pirate (JOI14_space_pirate) C++14
80 / 100
 2000 ms 93000 KB 
#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");
    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];
 
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];
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) {
	if (dist[x] == -1) {
		// cnt += sz(todo[dis[x]+cycLen]);
		trav(len,todo[dis[x]+cycLen]) {
			int l = dis[x]-disPath[x]+1, r = cycLen;
			l += len-1-cycLen, r += len-1-cycLen;
			if (l > maxDis[x] || l > r) break;
			int b = B2.query(l,r);
			ans[x] -= b;
			cnt ++; zero += b == 0;
		}
	} 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;
			if (l > maxDis[x] || l > r) break;
			ans[x] += B2.query(l,r);
		}
	} 
}

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 35 ms 33400 KB Output is correct
2 Correct 35 ms 33528 KB Output is correct
3 Correct 35 ms 33400 KB Output is correct
4 Correct 36 ms 33400 KB Output is correct
5 Correct 35 ms 33400 KB Output is correct
6 Correct 36 ms 33400 KB Output is correct
7 Correct 35 ms 33448 KB Output is correct
8 Correct 35 ms 33400 KB Output is correct
9 Correct 35 ms 33400 KB Output is correct
10 Correct 35 ms 33348 KB Output is correct
11 Correct 35 ms 33272 KB Output is correct
12 Correct 35 ms 33336 KB Output is correct
13 Correct 35 ms 33404 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 35 ms 33400 KB Output is correct
2 Correct 35 ms 33528 KB Output is correct
3 Correct 35 ms 33400 KB Output is correct
4 Correct 36 ms 33400 KB Output is correct
5 Correct 35 ms 33400 KB Output is correct
6 Correct 36 ms 33400 KB Output is correct
7 Correct 35 ms 33448 KB Output is correct
8 Correct 35 ms 33400 KB Output is correct
9 Correct 35 ms 33400 KB Output is correct
10 Correct 35 ms 33348 KB Output is correct
11 Correct 35 ms 33272 KB Output is correct
12 Correct 35 ms 33336 KB Output is correct
13 Correct 35 ms 33404 KB Output is correct
14 Correct 35 ms 33400 KB Output is correct
15 Correct 41 ms 34040 KB Output is correct
16 Correct 47 ms 34020 KB Output is correct
17 Correct 49 ms 34212 KB Output is correct
18 Correct 46 ms 34936 KB Output is correct
19 Correct 44 ms 34604 KB Output is correct
20 Correct 45 ms 34680 KB Output is correct
21 Correct 44 ms 34680 KB Output is correct
22 Correct 45 ms 34552 KB Output is correct
23 Correct 44 ms 34552 KB Output is correct
24 Correct 43 ms 34292 KB Output is correct
25 Correct 40 ms 34040 KB Output is correct
26 Correct 46 ms 34936 KB Output is correct
27 Correct 47 ms 34296 KB Output is correct
28 Correct 45 ms 34424 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 61000 KB Output is correct
2 Correct 1084 ms 92920 KB Output is correct
3 Correct 691 ms 77172 KB Output is correct
4 Correct 385 ms 61188 KB Output is correct
5 Correct 916 ms 93000 KB Output is correct
6 Correct 660 ms 76492 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 33400 KB Output is correct
2 Correct 35 ms 33528 KB Output is correct
3 Correct 35 ms 33400 KB Output is correct
4 Correct 36 ms 33400 KB Output is correct
5 Correct 35 ms 33400 KB Output is correct
6 Correct 36 ms 33400 KB Output is correct
7 Correct 35 ms 33448 KB Output is correct
8 Correct 35 ms 33400 KB Output is correct
9 Correct 35 ms 33400 KB Output is correct
10 Correct 35 ms 33348 KB Output is correct
11 Correct 35 ms 33272 KB Output is correct
12 Correct 35 ms 33336 KB Output is correct
13 Correct 35 ms 33404 KB Output is correct
14 Correct 35 ms 33400 KB Output is correct
15 Correct 41 ms 34040 KB Output is correct
16 Correct 47 ms 34020 KB Output is correct
17 Correct 49 ms 34212 KB Output is correct
18 Correct 46 ms 34936 KB Output is correct
19 Correct 44 ms 34604 KB Output is correct
20 Correct 45 ms 34680 KB Output is correct
21 Correct 44 ms 34680 KB Output is correct
22 Correct 45 ms 34552 KB Output is correct
23 Correct 44 ms 34552 KB Output is correct
24 Correct 43 ms 34292 KB Output is correct
25 Correct 40 ms 34040 KB Output is correct
26 Correct 46 ms 34936 KB Output is correct
27 Correct 47 ms 34296 KB Output is correct
28 Correct 45 ms 34424 KB Output is correct
29 Correct 385 ms 61000 KB Output is correct
30 Correct 1084 ms 92920 KB Output is correct
31 Correct 691 ms 77172 KB Output is correct
32 Correct 385 ms 61188 KB Output is correct
33 Correct 916 ms 93000 KB Output is correct
34 Correct 660 ms 76492 KB Output is correct
35 Correct 478 ms 59824 KB Output is correct
36 Correct 471 ms 60400 KB Output is correct
37 Correct 409 ms 58756 KB Output is correct
38 Correct 871 ms 90268 KB Output is correct
39 Correct 715 ms 77276 KB Output is correct
40 Correct 810 ms 87324 KB Output is correct
41 Correct 1024 ms 92612 KB Output is correct
42 Correct 754 ms 76980 KB Output is correct
43 Correct 706 ms 77732 KB Output is correct
44 Correct 642 ms 71256 KB Output is correct
45 Correct 440 ms 57932 KB Output is correct
46 Correct 1136 ms 90612 KB Output is correct
47 Execution timed out 2044 ms 69532 KB Time limit exceeded
48 Halted 0 ms 0 KB -