oj.uz

Submission #497228

# Submission time Handle Problem Language Result Execution time Memory
497228 2021-12-22T19:28:01 Z SirCovidThe19th Link (CEOI06_link) C++17
28 / 100
 339 ms 6272 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 304 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 2 ms 304 KB Output isn't correct
5 Incorrect 3 ms 332 KB Output isn't correct
6 Incorrect 15 ms 972 KB Output isn't correct
7 Incorrect 26 ms 1052 KB Output isn't correct
8 Incorrect 35 ms 1392 KB Output isn't correct
9 Correct 65 ms 1824 KB Output is correct
10 Incorrect 52 ms 1744 KB Output isn't correct
11 Correct 80 ms 2752 KB Output is correct
12 Correct 114 ms 2572 KB Output is correct
13 Incorrect 155 ms 3504 KB Output isn't correct
14 Incorrect 174 ms 3892 KB Output isn't correct
15 Correct 218 ms 4664 KB Output is correct
16 Incorrect 226 ms 5180 KB Output isn't correct
17 Incorrect 307 ms 5792 KB Output isn't correct
18 Incorrect 339 ms 5920 KB Output isn't correct
19 Incorrect 302 ms 5920 KB Output isn't correct
20 Incorrect 304 ms 5904 KB Output isn't correct
21 Incorrect 313 ms 6088 KB Output isn't correct
22 Incorrect 298 ms 6192 KB Output isn't correct
23 Correct 322 ms 6080 KB Output is correct
24 Correct 300 ms 6272 KB Output is correct
25 Incorrect 299 ms 6272 KB Output isn't correct