oj.uz

Submission #497276

# Submission time Handle Problem Language Result Execution time Memory
497276 2021-12-22T22:29:20 Z SirCovidThe19th Link (CEOI06_link) C++17
100 / 100
 369 ms 9272 KB 
#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 = i;
        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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct
3 Correct 2 ms 2216 KB Output is correct
4 Correct 3 ms 2228 KB Output is correct
5 Correct 3 ms 2252 KB Output is correct
6 Correct 16 ms 2912 KB Output is correct
7 Correct 27 ms 3296 KB Output is correct
8 Correct 40 ms 3756 KB Output is correct
9 Correct 64 ms 4356 KB Output is correct
10 Correct 54 ms 4272 KB Output is correct
11 Correct 87 ms 5692 KB Output is correct
12 Correct 115 ms 4876 KB Output is correct
13 Correct 143 ms 5864 KB Output is correct
14 Correct 209 ms 6316 KB Output is correct
15 Correct 218 ms 7176 KB Output is correct
16 Correct 250 ms 7960 KB Output is correct
17 Correct 323 ms 9012 KB Output is correct
18 Correct 331 ms 8928 KB Output is correct
19 Correct 325 ms 8952 KB Output is correct
20 Correct 319 ms 8928 KB Output is correct
21 Correct 328 ms 9248 KB Output is correct
22 Correct 338 ms 9212 KB Output is correct
23 Correct 334 ms 9052 KB Output is correct
24 Correct 369 ms 9172 KB Output is correct
25 Correct 361 ms 9272 KB Output is correct