oj.uz

답안 #136631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136631 2019-07-25T23:01:16 Z Benq 우주 해적 (JOI14_space_pirate) C++14
80 / 100
 2000 ms 93224 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;
 
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -