oj.uz

Submission #497250

# Submission time Handle Problem Language Result Execution time Memory
497250 2021-12-22T20:51:53 Z SirCovidThe19th Link (CEOI06_link) C++17
48 / 100
 361 ms 8460 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 stPos = 1e9, longest = -1, sz = nodes.size(); 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 = 0, pos = i, run = 0; i < sz * 2; i++, pos = i % sz){
        if (!ok[pos] and run > longest) stPos = pos, longest = run;
        run = (ok[pos] ? run + 1 : 0);
    }
    for (int i = stPos, pos = i, D = 2e9; i < sz * 2; i++, pos = i % sz){
        if (!ok[pos]){
            if (D > k) D = 1, ans++;
            ok[pos] = 1;
        }
        D++;
    }    
}

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
48.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2220 KB Output is correct
2 Correct 1 ms 2216 KB Output is correct
3 Incorrect 2 ms 2252 KB Output isn't correct
4 Correct 2 ms 2284 KB Output is correct
5 Incorrect 4 ms 2252 KB Output isn't correct
6 Incorrect 17 ms 2824 KB Output isn't correct
7 Incorrect 28 ms 3108 KB Output isn't correct
8 Incorrect 39 ms 3532 KB Output isn't correct
9 Correct 55 ms 4260 KB Output is correct
10 Correct 55 ms 4248 KB Output is correct
11 Correct 88 ms 5336 KB Output is correct
12 Correct 127 ms 5188 KB Output is correct
13 Correct 146 ms 5932 KB Output is correct
14 Incorrect 218 ms 6280 KB Output isn't correct
15 Correct 214 ms 6964 KB Output is correct
16 Correct 236 ms 7344 KB Output is correct
17 Incorrect 282 ms 8116 KB Output isn't correct
18 Incorrect 296 ms 8096 KB Output isn't correct
19 Incorrect 312 ms 8156 KB Output isn't correct
20 Incorrect 299 ms 8036 KB Output isn't correct
21 Incorrect 361 ms 8212 KB Output isn't correct
22 Incorrect 303 ms 8460 KB Output isn't correct
23 Correct 319 ms 8268 KB Output is correct
24 Correct 309 ms 8436 KB Output is correct
25 Incorrect 317 ms 8364 KB Output isn't correct