oj.uz

Submission #497240

# Submission time Handle Problem Language Result Execution time Memory
497240 2021-12-22T19:56:28 Z SirCovidThe19th Link (CEOI06_link) C++17
32 / 100
 307 ms 6608 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); 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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 292 KB Output isn't correct
4 Incorrect 2 ms 332 KB Output isn't correct
5 Incorrect 3 ms 332 KB Output isn't correct
6 Incorrect 15 ms 844 KB Output isn't correct
7 Incorrect 27 ms 1284 KB Output isn't correct
8 Incorrect 37 ms 1580 KB Output isn't correct
9 Correct 55 ms 2072 KB Output is correct
10 Incorrect 58 ms 2080 KB Output isn't correct
11 Correct 82 ms 3024 KB Output is correct
12 Correct 110 ms 2924 KB Output is correct
13 Incorrect 162 ms 3820 KB Output isn't correct
14 Incorrect 168 ms 4268 KB Output isn't correct
15 Correct 195 ms 5068 KB Output is correct
16 Incorrect 237 ms 5460 KB Output isn't correct
17 Incorrect 263 ms 6124 KB Output isn't correct
18 Incorrect 289 ms 6444 KB Output isn't correct
19 Incorrect 296 ms 6368 KB Output isn't correct
20 Incorrect 307 ms 6256 KB Output isn't correct
21 Incorrect 288 ms 6340 KB Output isn't correct
22 Incorrect 290 ms 6548 KB Output isn't correct
23 Correct 291 ms 6356 KB Output is correct
24 Correct 294 ms 6576 KB Output is correct
25 Incorrect 294 ms 6608 KB Output isn't correct