#include <bits/stdc++.h>
using namespace std;
const int mx = 5e5 + 5;
int n, k, ans, indeg[mx], nxt[mx], dst[mx]; bool vis[mx];
void solveIndeg0(){
queue<int> q; memset(dst, 0x3f, sizeof(dst));
dst[1] = 0;
for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);
while (!q.empty()){
int cur = q.front(), to = nxt[cur]; q.pop();
vis[cur] = 1;
if (dst[cur] > k) dst[cur] = 1, ans++;
dst[to] = min(dst[to], dst[cur] + 1);
if (!(--indeg[to])) q.push(to);
}
}
void solveCyc(int cur){
vector<int> nodes;
while (!vis[cur]) nodes.push_back(cur), vis[cur] = 1, cur = nxt[cur];
int sz = nodes.size(), jmp[sz], bst = 2e9; bool ok[sz] = {};
for (int i = 0, pos = i, D = 2e9; i < sz * 2; i++, pos = i % sz){
D = min(D + 1, dst[nodes[pos]]);
ok[pos] |= (D <= k);
}
for (int i = sz * 2 - 1, pos = i % sz, lst = 2e9; ~i; i--, pos = i % sz){
if (!ok[pos]) lst = pos;
jmp[pos] = lst - i;
}
for (int st = 0; st < min(sz, k); st++){
int trav = 0, tmp = 0;
while (1){
trav += jmp[(st + trav) % sz];
if (trav >= sz) break;
trav += k; tmp++;
}
bst = min(bst, tmp);
}
ans += bst;
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++){
int a, b; cin >> a >> b;
indeg[b]++; nxt[a] = b;
}
solveIndeg0();
for (int i = 1; i <= n; i++) if (!vis[i]) solveCyc(i);
cout<<ans<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2252 KB |
Output is correct |
2 |
Correct |
1 ms |
2252 KB |
Output is correct |
3 |
Correct |
2 ms |
2252 KB |
Output is correct |
4 |
Execution timed out |
1579 ms |
2236 KB |
Time limit exceeded |
5 |
Execution timed out |
1567 ms |
2252 KB |
Time limit exceeded |
6 |
Correct |
17 ms |
2820 KB |
Output is correct |
7 |
Correct |
31 ms |
3268 KB |
Output is correct |
8 |
Correct |
39 ms |
3768 KB |
Output is correct |
9 |
Correct |
58 ms |
4636 KB |
Output is correct |
10 |
Correct |
73 ms |
4520 KB |
Output is correct |
11 |
Correct |
85 ms |
6588 KB |
Output is correct |
12 |
Correct |
110 ms |
6576 KB |
Output is correct |
13 |
Correct |
163 ms |
8172 KB |
Output is correct |
14 |
Correct |
189 ms |
9276 KB |
Output is correct |
15 |
Correct |
207 ms |
10736 KB |
Output is correct |
16 |
Correct |
269 ms |
11448 KB |
Output is correct |
17 |
Correct |
295 ms |
12100 KB |
Output is correct |
18 |
Correct |
319 ms |
11964 KB |
Output is correct |
19 |
Correct |
332 ms |
12076 KB |
Output is correct |
20 |
Correct |
363 ms |
12080 KB |
Output is correct |
21 |
Correct |
326 ms |
12104 KB |
Output is correct |
22 |
Correct |
436 ms |
12180 KB |
Output is correct |
23 |
Correct |
331 ms |
12008 KB |
Output is correct |
24 |
Correct |
322 ms |
12224 KB |
Output is correct |
25 |
Correct |
338 ms |
12412 KB |
Output is correct |