Submission #497228

#	Time	Username	Problem	Language	Result	Execution time	Memory
497228		SirCovidThe19th	Link (CEOI06_link)	C++17	28 / 100	339 ms	6272 KiB

link

#include <bits/stdc++.h>
using namespace std; 

const int mx = 5e5 + 5;

int n, k, ans, indeg[mx], nxt[mx]; bool ok[mx], vis[mx]; 

void mustDrawEdge(int cur){
    int dst = k + (cur == 1);
    ans += (cur != 1);
    while (dst--) ok[cur] = 1, cur = nxt[cur];
}
void solveCyc(int cur){
    vector<int> nodes; 
    while (!vis[cur]) nodes.push_back(cur), vis[cur] = 1, cur = nxt[cur];

    int stPos, longest = -1, sz = nodes.size();
    for (int i = 0, run = 0; i < sz * 2; i++){
        int pos = i % sz, node = nodes[pos];

        if (!ok[node] and run > longest) stPos = pos, longest = run;
        run = (ok[node] ? run + 1 : 0);
    }
    for (int i = stPos, cnt = 0; i < sz * 2; i++){
        int pos = i % sz, node = nodes[pos];

        if (!ok[node]){
            if (cnt <= 0) cnt = k, ans++;
            ok[node] = 1;
        }
        cnt--;
    }    
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        int a, b; cin >> a >> b;
        indeg[b]++; nxt[a] = b;
    }
    for (int i = 1; i <= n; i++) if ((!indeg[i] and !ok[i]) or i == 1) mustDrawEdge(i);
    for (int i = 1; i <= n; i++) if (!ok[i]) solveCyc(i);

    cout<<ans<<endl;
}

Compilation message (stderr)

link.cpp: In function 'void solveCyc(int)':
link.cpp:24:5: warning: 'stPos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     for (int i = stPos, cnt = 0; i < sz * 2; i++){
      |     ^~~

• Subtask 1: 28 / 100