제출 #497240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497240		SirCovidThe19th	Link (CEOI06_link)	C++17	32 / 100	307 ms	6608 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); bool sub = (!indeg[cur]);
    ans += (cur != 1);
    while (dst--){
        ok[cur] = 1; cur = nxt[cur];

        indeg[cur] -= sub; 
        if (indeg[cur] != 0) sub = 0;
    }
}
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 32 / 100