Submission #497276

#	Time	Username	Problem	Language	Result	Execution time	Memory
497276		SirCovidThe19th	Link (CEOI06_link)	C++17	100 / 100	369 ms	9272 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 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 / 100