#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
/*const int MOD = 998244353;
inline int lgput(int a, int b) {
int ans = 1;
while(b > 0) {
if(b & 1) ans = (1LL * ans * a) % MOD;
b >>= 1;
a = (1LL * a * a) % MOD;
}
return ans;
}
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}
inline int inv(int x) {
return lgput(x, MOD - 2);
}*/
/*int fact[], invfact[];
inline void prec(int n) {
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
invfact[n] = lgput(fact[n], MOD - 2);
for(int i = n - 1; i >= 0; i--) {
invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
}
}
inline int comb(int n, int k) {
if(n < k) return 0;
return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/
using namespace std;
const int INF = 1e9;
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, j, n, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
vector < vector <int> > g(n + 1);
vector <int> to(n + 1), deg(n + 1);
for(i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
to[a] = b, deg[b]++;
g[b].push_back(a);
}
vector <int> dst(n + 1, INF), vis(n + 1);
queue <int> Q;
int ans = 0;
for(i = 1; i <= n; i++) {
if(deg[i] == 0) {
Q.push(i);
dst[i] = 1;
ans += (i != 1);
}
}
dst[1] = 0;
while(Q.size()) {
int nod = Q.front();
vis[nod] = 1;
Q.pop();
for(auto it : g[nod]) {
dst[nod] = min(dst[nod], dst[it] + 1);
}
if(dst[nod] == k + 1) {
dst[nod] = 1;
ans++;
}
deg[to[nod]]--;
if(deg[to[nod]] == 0) {
Q.push(to[nod]);
}
}
//cerr << ans;
for(i = 1; i <= n; i++) {
for(auto it : g[i]) {
dst[i] = min(dst[i], dst[it] + 1);
}
}
for(i = 1; i <= n; i++) {
if(vis[i]) continue;
vector <int> cyc;
for(j = i; vis[j] == 0; j = to[j]) {
vis[j] = 1;
cyc.push_back(j);
}
priority_queue < pair <int, int> > pq;
int sz = cyc.size();
for(j = 0; j < sz; j++) {
cyc.push_back(cyc[j]);
pq.push({-dst[cyc[j]], cyc[j]});
}
while(pq.size()) {
auto cur = pq.top();
pq.pop();
if(dst[to[cur.second]] > -cur.first + 1) {
dst[to[cur.second]] = -cur.first + 1;
pq.push({cur.first - 1, to[cur.second]});
}
}
vector <int> nxt(2 * sz);
int last = -1;
for(j = 2 * sz - 1; j >= 0; j--) {
if(dst[cyc[j]] > k) {
last = j;
}
nxt[j] = last;
}
vector < vector <int> > anc(20, vector <int>(2 * sz));
for(j = 0; j < 2 * sz; j++) {
anc[0][j] = (j + k < 2 * sz ? nxt[j + k] : -1);
}
for(int bit = 1; bit < 20; bit++) {
for(j = 0; j < 2 * sz; j++) {
anc[bit][j] = (anc[bit - 1][j] == -1 ? -1 : anc[bit - 1][anc[bit - 1][j]]);
}
}
int mn = INF;
for(j = 0; j < sz; j++) {
if(dst[cyc[j]] <= k) continue;
int cur = 0, p = j;
for(int bit = 19; bit >= 0; bit--) {
if(anc[bit][p] != -1 && anc[bit][p] < j + sz) {
p = anc[bit][p];
cur += (1 << bit);
}
}
mn = min(mn, cur + 1);
}
if(mn == INF) mn = 0;
ans += mn;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
5 ms |
636 KB |
Output is correct |
| 5 |
Correct |
5 ms |
632 KB |
Output is correct |
| 6 |
Correct |
24 ms |
3480 KB |
Output is correct |
| 7 |
Correct |
34 ms |
4600 KB |
Output is correct |
| 8 |
Correct |
53 ms |
7296 KB |
Output is correct |
| 9 |
Correct |
82 ms |
13164 KB |
Output is correct |
| 10 |
Correct |
72 ms |
11912 KB |
Output is correct |
| 11 |
Correct |
202 ms |
35564 KB |
Output is correct |
| 12 |
Correct |
193 ms |
15240 KB |
Output is correct |
| 13 |
Correct |
296 ms |
27500 KB |
Output is correct |
| 14 |
Correct |
299 ms |
30900 KB |
Output is correct |
| 15 |
Correct |
466 ms |
40300 KB |
Output is correct |
| 16 |
Correct |
429 ms |
47436 KB |
Output is correct |
| 17 |
Correct |
573 ms |
48108 KB |
Output is correct |
| 18 |
Correct |
537 ms |
45028 KB |
Output is correct |
| 19 |
Correct |
687 ms |
46848 KB |
Output is correct |
| 20 |
Correct |
621 ms |
47008 KB |
Output is correct |
| 21 |
Correct |
603 ms |
50908 KB |
Output is correct |
| 22 |
Correct |
608 ms |
51076 KB |
Output is correct |
| 23 |
Correct |
535 ms |
50756 KB |
Output is correct |
| 24 |
Correct |
616 ms |
51068 KB |
Output is correct |
| 25 |
Correct |
651 ms |
51068 KB |
Output is correct |
