Submission #497225

#	Time	Username	Problem	Language	Result	Execution time	Memory
497225		SirCovidThe19th	Link (CEOI06_link)	C++17	48 / 100	333 ms	12700 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; int stPos, longest = -1;

    while (!vis[cur]) nodes.push_back(cur), vis[cur] = 1, cur = nxt[cur];

    for (int i = 0, run = 0; i < nodes.size() * 2; i++){
        int pos = i % nodes.size(), 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 < nodes.size() * 2; i++){
        int pos = i % nodes.size(), node = nodes[pos];

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

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:18:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0, run = 0; i < nodes.size() * 2; i++){
      |                              ~~^~~~~~~~~~~~~~~~~~
link.cpp:24:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = stPos, cnt = 0; i < nodes.size() * 2; i++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
link.cpp:24:34: warning: 'stPos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     for (int i = stPos, cnt = 0; i < nodes.size() * 2; i++){
      |                                  ^

• Subtask 1: 48 / 100