oj.uz

Submission #56750

# Submission time Handle Problem Language Result Execution time Memory
56750 2018-07-12T11:37:04 Z win11905 Teleporters (IOI08_teleporters) C++11
90 / 100
 1000 ms 66252 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 2e6+5;

int n, m, V[N], val[N], neibour[N], Com[N], psz, pz1;
bool Check[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        neibour[u] = v, neibour[v] = u;
        V[u]++, V[v]++;
    }
    for(int i = 1; i < N; ++i) {
        V[i] += V[i-1];
        if(V[i] != V[i-1]) Com[pz1++] = i;
    }
    int cnt = 0, p = 0; Check[0] = true;
    while(p != (n<<1)) Check[p = V[neibour[Com[p]]]] = true, cnt++;
    for(int i = 1; i <= (n<<1); ++i) if(!Check[i]) {
        int u = i, sz = 0; Check[u] = true;
        do Check[u = V[neibour[Com[u]]]] = true, sz++; while(u != i);
        val[++psz] = sz;
    }
    sort(val+1, val + psz + 1, greater<int>()); for(int i = 1; i <= psz; ++i) val[i] += val[i-1]; 
    cnt += val[min(psz, m)] + 2 * min(psz, m);
    if(m > psz) m -= psz, cnt += ((m>>1)<<2) + (m & 1);
    printf("%d\n", cnt);
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
teleporters.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8080 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8168 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8300 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8300 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8328 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8344 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8344 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8372 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8412 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8472 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8600 KB Output is correct
2 Correct 26 ms 8888 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8888 KB Output is correct
2 Correct 29 ms 9432 KB Output is correct
3 Correct 37 ms 9704 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9704 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9876 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 14552 KB Output is correct
2 Correct 387 ms 25504 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 25704 KB Output is correct
2 Correct 600 ms 37732 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 49596 KB Output is correct
2 Correct 778 ms 51552 KB Output is correct
3 Correct 659 ms 63796 KB Output is correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1034 ms 64036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 66252 KB Time limit exceeded
2 Halted 0 ms 0 KB -