| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25801 |
2017-06-24T07:42:45 Z |
범수사생팬(#1085) |
Space Pirate (JOI14_space_pirate) |
C++14 |
|
73 ms |
35272 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 100005;
struct disj{
int pa[MAXN], sz[MAXN];
void init(int n){
for(int i=0; i<=n; i++){
pa[i] = i;
sz[i] = 1;
}
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p;
sz[p] += sz[q];
return 1;
}
}disj;
lint k;
int n, a[100005];
int par[60][100005];
vector<int> gph[100005];
int anc(int x, lint k){
for(int i=0; k; i++){
if((k >> i) & 1){
k ^= (1 << i);
x = par[i][x];
}
}
return x;
}
lint ans[100005];
int cnt[100005], up[100005], lev[100005], cmp[100005];
int din[100005], dout[100005], piv;
bool sub(int s, int t){
return din[s] <= din[t] && dout[t] <= dout[s];
}
void dfs(int x, int p){
din[x] = piv++;
for(auto &i : gph[x]){
if(i != p && cnt[i] == 1){
lev[i] = lev[x] + 1;
cmp[i] = cmp[x];
dfs(i, x);
}
}
dout[x] = piv;
}
int main(){
scanf("%d %lld",&n,&k);
disj.init(n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
gph[a[i]].push_back(i);
disj.uni(i, a[i]);
par[0][i] = a[i];
}
for(int i=1; i<60; i++){
for(int j=1; j<=n; j++){
par[i][j] = par[i-1][par[i-1][j]];
}
}
int idx = 0, st = 1e9, ed = -1e9;
for(int p=1; cnt[p]<2; p=a[p]) cnt[p]++;
for(int p=1; !up[p]; p=a[p]) up[p] = ++idx;
for(int i=1; i<=n; i++){
if(cnt[i] == 2){
st = min(st, up[i]);
ed = max(ed, up[i]);
cmp[i] = i;
dfs(i, -1);
}
}
for(int i=1; i<=n; i++){
if(cnt[i] == 0) ans[anc(1, k)] += n;
if(cnt[i] == 1){
if(k < up[i]){
ans[anc(1, k)] += n;
continue;
}
for(int j=1; j<=n; j++){
if(sub(i, j)){
lint t = k - up[i] + 1;
if(t < 0) ans[anc(1, k)]++;
else{
t %= lev[j] - lev[i] + 1;
if(t == 0) ans[i]++;
else ans[anc(j, t - 1)]++;
}
}
else{
if(k >= up[i]) ans[anc(j, k - up[i])]++;
else ans[anc(1, k)]++;
}
}
}
if(cnt[i] == 2){
if(k < up[i]){
ans[anc(1, k)] += n;
continue;
}
for(int j=1; j<=n; j++){
if(disj.find(j) != disj.find(1)){
ans[anc(j, k - up[i])]++;
}
else if(cnt[j] == 2){
if(up[i] < up[j]){
lint t = k - up[i] + 1;
t %= (ed - st + 1) - (up[j] - up[i] - 1);
if(t == 0) ans[i]++;
else ans[anc(j, t - 1)]++;
}
else{
lint t = k - up[i] + 1;
t %= up[i] - up[j] + 1;
if(t == 0) ans[i]++;
else ans[anc(j, t - 1)]++;
}
}
else{
if(up[i] < up[cmp[j]]){
lint t = k - up[i] + 1;
t %= (ed - st + 1) - (up[cmp[j]] - up[i] - 1) + lev[j];
if(t == 0) ans[i]++;
else ans[anc(j, t - 1)]++;
}
else{
lint t = k - up[i] + 1;
t %= (up[i] - up[cmp[j]] + 1) + lev[j];
if(t == 0) ans[i]++;
else ans[anc(j, t - 1)]++;
}
}
}
}
}
for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}
Compilation message
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:66:24: 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:69:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
32104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
32236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
35272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
34084 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
