oj.uz

Submission #217546

# Submission time Handle Problem Language Result Execution time Memory
217546 2020-03-30T08:26:06 Z mhy908 Teleporters (IOI08_teleporters) C++14
100 / 100
 493 ms 30356 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const int st=1, fin=4000002, MAXN=2000000;
int n;
LL k, ans;
bool ch[2000010], ch2[2000010];
int link[4000010];
LL dfs(int num, int finnum){
    //printf("! %d %d\n", num, finnum);
    if(num%2==0)ch2[num/2]=true;
    if(num==finnum)return 0;
    return 1+dfs(link[num], finnum);
}
vector<LL> vc;
int main(){
    scanf("%d %lld", &n, &k);
    for(int i=1; i<=n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        link[2*a]=2*b+1;
        link[2*b]=2*a+1;
        ch[a]=ch[b]=true;
    }
    ch[MAXN+1]=true;
    int pv=0;
    for(int i=1; i<=MAXN+1; i++){
        if(ch[i]){
            link[2*pv+1]=2*i;
            pv=i;
        }
    }
    ans=dfs(st, fin)/2;
    for(int i=1; i<=MAXN; i++){
        if(!ch[i]||ch2[i])continue;
        vc.pb((dfs(link[2*i], 2*i)+1)/2);
    }
    sort(all(vc), greater<LL>());
    for(auto i:vc){
        ans+=i+2;
        k--;
        if(!k)break;
    }
    ans+=(k+1)/2+k/2*3;
    printf("%lld", ans);
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
teleporters.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 392 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 14 ms 1736 KB Output is correct
3 Correct 18 ms 1280 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 768 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7156 KB Output is correct
2 Correct 190 ms 18920 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 14836 KB Output is correct
2 Correct 270 ms 22504 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 25576 KB Output is correct
2 Correct 383 ms 25576 KB Output is correct
3 Correct 361 ms 26212 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 25444 KB Output is correct
2 Correct 471 ms 25576 KB Output is correct
3 Correct 426 ms 21496 KB Output is correct
4 Correct 427 ms 21368 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 29536 KB Output is correct
2 Correct 485 ms 30104 KB Output is correct
3 Correct 292 ms 29660 KB Output is correct
4 Correct 460 ms 30356 KB Output is correct