#include <bits/stdc++.h>
using namespace std;
#define sz(V) ((int)V.size())
const int _N = 500001, DBG = 0;
bool chk[_N];
int N, K, A[_N], vs[_N], dep[_N], rt[_N], rid[_N], ith[_N], p[8][_N], cs[8][_N], ans;
vector<vector<int> > R;
vector<int> S, G[_N];
void go(int x, int col) {
S.push_back(x);
vs[x] = col;
if(vs[A[x]]) {
if(vs[A[x]] == col) {
vector<int> T;
while(1) {
int tmp = S.back(); S.pop_back();
T.push_back(tmp);
if(tmp == A[x]) break;
}
reverse(T.begin(), T.end());
for(int i=0; i<T.size(); i++) rid[T[i]] = sz(R), ith[T[i]] = i+1;
R.push_back(T);
}
}
else go(A[x], col);
}
int mrk(int x, int k) {
if(k <= 0) return x;
chk[x] = 1;
int d;
if(ith[x]) {
if(ith[x] < ith[A[x]]) d = ith[A[x]] - ith[x];
else d = ith[A[x]] - ith[x] + sz(R[rid[x]]);
}
else if(ith[A[x]]) return A[x] = mrk(rt[x], k - dep[x]);
else d = dep[x] - dep[A[x]];
return A[x] = mrk(A[x], k - d);
}
void dfs(int RT, int x, int d) {
// printf("dfs: x: %d, d: %d\n", x, d);
dep[x] = d; rt[x] = RT;
for(auto& it: G[x]) dfs(RT, it, d+1);
}
void showstat() {
puts("Showing...");
printf("answer: %d\n", ans);
for(int i=1; i<=N; i++) printf("%d", chk[i]);
puts("\n---------------------");
}
int main() {
vector<int> Q;
scanf("%d%d",&N,&K);
for(int i=1; i<=N; i++) {
int a, b; scanf("%d%d",&a,&b);
A[a] = b;
}
for(int i=1; i<=N; i++) if(!vs[i]) go(i, i);
for(int i=1; i<=N; i++) if(!ith[i]) {
G[A[i]].push_back(i);
Q.push_back(i);
}
for(int i=1; i<=N; i++) if(ith[i]) dfs(i, i, 0);
chk[1] = 1;
mrk(A[1], K);
if(DBG) showstat();
sort(Q.begin(), Q.end(), [&](int PP, int QQ) { return dep[PP] > dep[QQ]; });
for(auto& it: Q) {
if(chk[it]) continue;
mrk(it, K); ++ans;
}
if(DBG) showstat();
set<int> st;
for(auto& it: R) {
st.clear();
int M = sz(it);
for(int j=0; j<M; j++) {
p[0][j] = j; cs[0][j] = 0;
if(!chk[it[j]]) st.insert(j);
}
if(st.empty()) continue;
for(auto& jt: st) {
if(jt <= M-K) {
auto kt = st.lower_bound(jt + K);
if(kt == st.end()) {
p[0][jt] = *st.begin();
cs[0][jt] = *st.begin() - jt + M;
}
else {
p[0][jt] = *kt;
cs[0][jt] = *kt - jt;
}
}
else {
auto kt = st.lower_bound(jt + K - M);
if(kt == st.end()) p[0][jt] = jt, cs[0][jt] = M;
else p[0][jt] = *kt, cs[0][jt] = *kt - jt + M;
}
// printf("next[%d]: %d, cost: %d\n", jt, p[0][jt], cs[0][jt]);
}
int L;
for(int i=1; (1<<i)<=M; i++) {
for(int j=0; j<M; j++) {
p[i][j] = p[i-1][p[i-1][j]];
cs[i][j] = cs[i-1][j] + cs[i-1][p[i-1][j]];
cs[i][j] = min(cs[i][j], M);
}
L = i;
}
int mn = 1e9;
for(auto& jt: st) {
int sum = 0, now = jt, cnt = 0;
for(int j=L; j>=0; j--) if(sum + cs[j][now] < M) {
sum += cs[j][now], cnt += (1<<j), now = p[j][now];
// printf("now: %d, sum: %d, cnt: %d\n", now, sum, cnt);
}
mn = min(mn, cnt + 1);
// printf("jt: %d, cnt: %d\n", jt, cnt + 1);
}
ans += mn;
}
printf("%d", ans);
return 0;
}
Compilation message
link.cpp: In function 'void go(int, int)':
link.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<T.size(); i++) rid[T[i]] = sz(R), ith[T[i]] = i+1;
~^~~~~~~~~
link.cpp: In function 'int main()':
link.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&K);
~~~~~^~~~~~~~~~~~~~
link.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
link.cpp:122:43: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
sum += cs[j][now], cnt += (1<<j), now = p[j][now];
~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12280 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12280 KB |
Output is correct |
| 4 |
Correct |
14 ms |
12408 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12536 KB |
Output is correct |
| 6 |
Incorrect |
31 ms |
14712 KB |
Output isn't correct |
| 7 |
Correct |
43 ms |
15732 KB |
Output is correct |
| 8 |
Incorrect |
59 ms |
17780 KB |
Output isn't correct |
| 9 |
Correct |
88 ms |
23240 KB |
Output is correct |
| 10 |
Incorrect |
110 ms |
22376 KB |
Output isn't correct |
| 11 |
Runtime error |
237 ms |
89836 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
171 ms |
23716 KB |
Output isn't correct |
| 13 |
Runtime error |
262 ms |
69512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
313 ms |
78808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
337 ms |
83808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
450 ms |
108796 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
392 ms |
86704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
488 ms |
97476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
486 ms |
97080 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
489 ms |
94568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
468 ms |
98692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
474 ms |
98496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
656 ms |
113704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 24 |
Runtime error |
582 ms |
98756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 25 |
Runtime error |
539 ms |
103364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
