Submission #497250

#	Time	Username	Problem	Language	Result	Execution time	Memory
497250		SirCovidThe19th	Link (CEOI06_link)	C++17	48 / 100	361 ms	8460 KiB

link

#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 / 100