oj.uz

Submission #497225

# Submission time Handle Problem Language Result Execution time Memory
497225 2021-12-22T19:11:14 Z SirCovidThe19th Link (CEOI06_link) C++17
48 / 100
 333 ms 12700 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; 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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 280 KB Output isn't correct
2 Incorrect 1 ms 284 KB Output isn't correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 2 ms 316 KB Output isn't correct
5 Incorrect 3 ms 312 KB Output isn't correct
6 Correct 15 ms 912 KB Output is correct
7 Correct 25 ms 1388 KB Output is correct
8 Correct 35 ms 1860 KB Output is correct
9 Correct 52 ms 2616 KB Output is correct
10 Incorrect 50 ms 2636 KB Output isn't correct
11 Correct 85 ms 4204 KB Output is correct
12 Incorrect 119 ms 4808 KB Output isn't correct
13 Incorrect 137 ms 6332 KB Output isn't correct
14 Incorrect 209 ms 7588 KB Output isn't correct
15 Correct 233 ms 8904 KB Output is correct
16 Incorrect 276 ms 10064 KB Output isn't correct
17 Correct 282 ms 11688 KB Output is correct
18 Incorrect 311 ms 12244 KB Output isn't correct
19 Incorrect 315 ms 12220 KB Output isn't correct
20 Correct 310 ms 12148 KB Output is correct
21 Incorrect 333 ms 12384 KB Output isn't correct
22 Correct 311 ms 12616 KB Output is correct
23 Correct 280 ms 12356 KB Output is correct
24 Correct 326 ms 12700 KB Output is correct
25 Incorrect 326 ms 12572 KB Output isn't correct