| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136301 |
2019-07-25T06:00:42 Z |
이온조(#3259) |
Link (CEOI06_link) |
C++14 |
|
615 ms |
62068 KB |
#include <bits/stdc++.h>
using namespace std;
#define sz(V) ((int)V.size())
const int _N = 500009, DBG = 0;
bool chk[_N];
int N, K, A[_N], vs[_N], dep[_N], rt[_N], rid[_N], ith[_N], p[22][_N], cs[22][_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();
for(auto& it: R) {
set<int> st;
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:120:43: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
sum += cs[j][now], cnt += (1<<j), now = p[j][now];
~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12280 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12280 KB |
Output is correct |
| 4 |
Correct |
14 ms |
12404 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12536 KB |
Output is correct |
| 6 |
Correct |
34 ms |
14972 KB |
Output is correct |
| 7 |
Correct |
44 ms |
15988 KB |
Output is correct |
| 8 |
Correct |
60 ms |
18280 KB |
Output is correct |
| 9 |
Correct |
93 ms |
24904 KB |
Output is correct |
| 10 |
Correct |
112 ms |
23748 KB |
Output is correct |
| 11 |
Correct |
168 ms |
53356 KB |
Output is correct |
| 12 |
Correct |
210 ms |
23936 KB |
Output is correct |
| 13 |
Correct |
242 ms |
37712 KB |
Output is correct |
| 14 |
Correct |
290 ms |
42272 KB |
Output is correct |
| 15 |
Correct |
387 ms |
49140 KB |
Output is correct |
| 16 |
Correct |
419 ms |
61128 KB |
Output is correct |
| 17 |
Correct |
469 ms |
53836 KB |
Output is correct |
| 18 |
Correct |
556 ms |
52032 KB |
Output is correct |
| 19 |
Correct |
541 ms |
52784 KB |
Output is correct |
| 20 |
Correct |
545 ms |
50908 KB |
Output is correct |
| 21 |
Correct |
554 ms |
57544 KB |
Output is correct |
| 22 |
Correct |
615 ms |
59400 KB |
Output is correct |
| 23 |
Correct |
584 ms |
62068 KB |
Output is correct |
| 24 |
Correct |
541 ms |
59276 KB |
Output is correct |
| 25 |
Correct |
537 ms |
58412 KB |
Output is correct |
