oj.uz

Submission #1016872

# Submission time Handle Problem Language Result Execution time Memory
1016872 2024-07-08T14:08:07 Z Andrey Closing Time (IOI23_closing) C++17
52 / 100
 92 ms 33876 KB 
#include "closing.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

long long n,x,y,k;
vector<pair<long long,long long>> haha[200001];
vector<long long> bruh(200001);
vector<long long> wow(200001);
vector<pair<long long,long long>> idk(0);

void dfs(long long a, long long t, long long d, bool yeah) {
    if(yeah) {
        bruh[a] = d;
    }
    else {
        wow[a] = d;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+v.second,yeah);
        }
    }
}

bool dude(long long a, long long t) {
    if(a == y) {
        if(bruh[a] < wow[a]) {
            k-=bruh[a];
            wow[a]-=bruh[a];
            bruh[a] = 0;
        }
        else {
            k-=wow[a];
            bruh[a]-=wow[a];
            wow[a] = 0;
        }
        return true;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            if(dude(v.first,a)) {
                if(bruh[a] < wow[a]) {
                    k-=bruh[a];
                    wow[a]-=bruh[a];
                    bruh[a] = 0;
                }
                else {
                    k-=wow[a];
                    bruh[a]-=wow[a];
                    wow[a] = 0;
                }
                return true;
            }
        }
    }
    return false;
}

long long solve() {
    long long sb = 0;
    vector<int> ans(n+1,-1);
    priority_queue<pair<long long,pair<long long,long long>>> no;
    priority_queue<pair<long long,pair<long long,long long>>> rem;
    priority_queue<pair<long long,long long>> dv;
    no.push({-LLONG_MAX/3,{n,-1}});
    rem.push({-LLONG_MAX/3,{n,-1}});
    dv.push({-LLONG_MAX/3,-1});
    for(int i = 0; i < n; i++) {
        ans[i] = 0;
        no.push({-idk[i].first,{i,0}});
        dv.push({-idk[i].second-idk[i].first,i});
    }
    for(int i = 0; i < 2*n; i++) {
        while(ans[no.top().second.first] != no.top().second.second) {
            no.pop();
        }
        while(ans[rem.top().second.first] != rem.top().second.second) {
            rem.pop();
        }
        while(dv.top().second != -1 && ans[dv.top().second] != 0) {
            dv.pop();
        }
        if(-dv.top().first-rem.top().first < -no.top().first) {
            long long p1 = rem.top().second.first,p2 = dv.top().second,c = -dv.top().first-rem.top().first;
            ans[p1]--;
            ans[p2]+=2;
            sb+=c;
            rem.push({idk[p2].second,{p2,2}});
            if(ans[p1] == 1) {
                rem.push({idk[p1].first,{p1,1}});
                no.push({-idk[p1].second,{p1,1}});
            }
            else {
                no.push({-idk[p1].first,{p1,0}});
                dv.push({-idk[p1].second,p1});
            }
        }
        else {
            ans[no.top().second.first]++;
            long long c,p = no.top().second.first;
            if(no.top().second.second == 1) {
                c = idk[p].second;
            }
            else {
                c = idk[p].first;
                no.push({-idk[p].second,{p,ans[p]}});
            }
            sb+=c;
            rem.push({c,{p,ans[p]}});
        }
        if(sb > k) {
            return i;
        }
    }
    return 2*n;
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    x = X;
    y = Y;
    k = K;
    for(int i = 0; i < n; i++) {
        haha[i].clear();
    }
    for(long long i = 0; i < n-1; i++) {
        haha[U[i]].push_back({V[i],W[i]});
        haha[V[i]].push_back({U[i],W[i]});
    }
    long long ans = 0;
    dfs(x,-1,0,true);
    dfs(y,-1,0,false);
    vector<long long> wut(n);
    for(long long i = 0; i < n; i++) {
        wut[i] = min(bruh[i],wow[i]);
    }
    sort(wut.begin(),wut.end());
    long long sb = 0;
    for(long long i = 0; i < wut.size(); i++) {
        sb+=wut[i];
        if(sb > k) {
            break;
        }
        ans++;
    }
    dude(x,-1);
    if(k < 0) {
        return ans;
    }
    idk.clear();
    for(int i = 0; i < n; i++) {
        idk.push_back({min(bruh[i],wow[i]),max(bruh[i],wow[i])-min(bruh[i],wow[i])});
    }
    return max(solve(),ans);
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:140:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(long long i = 0; i < wut.size(); i++) {
      |                          ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 29060 KB Output is correct
2 Correct 92 ms 33876 KB Output is correct
3 Correct 47 ms 10832 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8052 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 2 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 3 ms 8280 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8052 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 2 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 3 ms 8280 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 4 ms 8284 KB Output is correct
26 Correct 4 ms 8860 KB Output is correct
27 Correct 4 ms 8792 KB Output is correct
28 Correct 4 ms 9212 KB Output is correct
29 Correct 4 ms 9052 KB Output is correct
30 Correct 3 ms 8544 KB Output is correct
31 Correct 3 ms 8540 KB Output is correct
32 Correct 3 ms 8552 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8108 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 4 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 3 ms 8280 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8284 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 3 ms 8280 KB Output is correct
22 Correct 3 ms 8124 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8052 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8108 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 4 ms 8284 KB Output is correct
25 Correct 2 ms 8284 KB Output is correct
26 Correct 3 ms 8280 KB Output is correct
27 Correct 2 ms 8284 KB Output is correct
28 Correct 2 ms 8284 KB Output is correct
29 Correct 2 ms 8028 KB Output is correct
30 Correct 2 ms 8284 KB Output is correct
31 Correct 2 ms 8284 KB Output is correct
32 Correct 2 ms 8284 KB Output is correct
33 Correct 3 ms 8280 KB Output is correct
34 Correct 3 ms 8124 KB Output is correct
35 Correct 2 ms 8284 KB Output is correct
36 Correct 2 ms 8284 KB Output is correct
37 Incorrect 2 ms 8284 KB 3rd lines differ - on the 1st token, expected: '24', found: '25'
38 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8052 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 3 ms 8280 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 3 ms 8284 KB Output is correct
27 Correct 2 ms 8284 KB Output is correct
28 Correct 2 ms 8028 KB Output is correct
29 Correct 2 ms 8108 KB Output is correct
30 Correct 2 ms 8284 KB Output is correct
31 Correct 4 ms 8284 KB Output is correct
32 Correct 2 ms 8284 KB Output is correct
33 Correct 3 ms 8280 KB Output is correct
34 Correct 2 ms 8284 KB Output is correct
35 Correct 2 ms 8284 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8284 KB Output is correct
38 Correct 2 ms 8284 KB Output is correct
39 Correct 2 ms 8284 KB Output is correct
40 Correct 3 ms 8280 KB Output is correct
41 Correct 3 ms 8124 KB Output is correct
42 Correct 2 ms 8284 KB Output is correct
43 Correct 2 ms 8284 KB Output is correct
44 Incorrect 2 ms 8284 KB 3rd lines differ - on the 1st token, expected: '24', found: '25'
45 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8052 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 3 ms 8280 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 4 ms 8284 KB Output is correct
27 Correct 4 ms 8860 KB Output is correct
28 Correct 4 ms 8792 KB Output is correct
29 Correct 4 ms 9212 KB Output is correct
30 Correct 4 ms 9052 KB Output is correct
31 Correct 3 ms 8544 KB Output is correct
32 Correct 3 ms 8540 KB Output is correct
33 Correct 3 ms 8552 KB Output is correct
34 Correct 3 ms 8284 KB Output is correct
35 Correct 2 ms 8284 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8108 KB Output is correct
38 Correct 2 ms 8284 KB Output is correct
39 Correct 4 ms 8284 KB Output is correct
40 Correct 2 ms 8284 KB Output is correct
41 Correct 3 ms 8280 KB Output is correct
42 Correct 2 ms 8284 KB Output is correct
43 Correct 2 ms 8284 KB Output is correct
44 Correct 2 ms 8028 KB Output is correct
45 Correct 2 ms 8284 KB Output is correct
46 Correct 2 ms 8284 KB Output is correct
47 Correct 2 ms 8284 KB Output is correct
48 Correct 3 ms 8280 KB Output is correct
49 Correct 3 ms 8124 KB Output is correct
50 Correct 2 ms 8284 KB Output is correct
51 Correct 2 ms 8284 KB Output is correct
52 Incorrect 2 ms 8284 KB 3rd lines differ - on the 1st token, expected: '24', found: '25'
53 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8052 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 2 ms 8284 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 3 ms 8280 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 4 ms 8284 KB Output is correct
27 Correct 4 ms 8860 KB Output is correct
28 Correct 4 ms 8792 KB Output is correct
29 Correct 4 ms 9212 KB Output is correct
30 Correct 4 ms 9052 KB Output is correct
31 Correct 3 ms 8544 KB Output is correct
32 Correct 3 ms 8540 KB Output is correct
33 Correct 3 ms 8552 KB Output is correct
34 Correct 3 ms 8284 KB Output is correct
35 Correct 2 ms 8284 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8108 KB Output is correct
38 Correct 2 ms 8284 KB Output is correct
39 Correct 4 ms 8284 KB Output is correct
40 Correct 2 ms 8284 KB Output is correct
41 Correct 3 ms 8280 KB Output is correct
42 Correct 2 ms 8284 KB Output is correct
43 Correct 2 ms 8284 KB Output is correct
44 Correct 2 ms 8028 KB Output is correct
45 Correct 2 ms 8284 KB Output is correct
46 Correct 2 ms 8284 KB Output is correct
47 Correct 2 ms 8284 KB Output is correct
48 Correct 3 ms 8280 KB Output is correct
49 Correct 3 ms 8124 KB Output is correct
50 Correct 2 ms 8284 KB Output is correct
51 Correct 2 ms 8284 KB Output is correct
52 Incorrect 2 ms 8284 KB 3rd lines differ - on the 1st token, expected: '24', found: '25'
53 Halted 0 ms 0 KB -