oj.uz

Submission #1012630

# Submission time Handle Problem Language Result Execution time Memory
1012630 2024-07-02T12:31:31 Z JakobZorz Closing Time (IOI23_closing) C++17
43 / 100
 86 ms 36812 KB 
#include"closing.h"
#include<vector>
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;

int n,x,y;
ll k;
vector<pair<int,int>>nodes[200000];
ll distx[200000];
ll disty[200000];

void dfs1(int node,int par,ll*dists){
    for(auto[ne,w]:nodes[node]){
        if(ne==par)
            continue;
        dists[ne]=dists[node]+w;
        dfs1(ne,node,dists);
    }
}

int lvl1(){
    vector<bool>vis(n);
    int res=0;
    ll kr=k;
    priority_queue<pair<ll,int>>q;
    q.push({0,x});
    q.push({0,y});
    vis[x]=true;
    vis[y]=true;
    while(q.size()){
        int node=q.top().second;
        ll cost=-q.top().first;
        q.pop();
        if(cost>kr)
            break;
        res++;
        kr-=cost;
        for(auto[ne,w]:nodes[node]){
            if(vis[ne])
                continue;
            vis[ne]=true;
            q.push({-min(distx[ne],disty[ne]),ne});
        }
    }
    return res;
}

int get(multiset<ll>&s,ll money){
    int res=0;
    for(ll i:s){
        if(i>money)
            break;
        res++;
        money-=i;
    }
    return res;
}

int solve(vector<pair<ll,ll>>opts,ll money){
    for(auto&[i,j]:opts)
        swap(i,j);
    sort(opts.begin(),opts.end());
    for(auto&[i,j]:opts)
        swap(i,j);
    
    multiset<ll>s;
    for(auto[i,j]:opts)
        s.insert(i);
    
    int res=get(s,money);
    int res2=0;
    for(auto[i,j]:opts){
        money-=i;
        s.erase(s.find(i));
        s.insert(j);
        res2++;
        if(money<0)
            break;
        res=max(res,res2+get(s,money));
    }
    return res;
}

int lvl2(){
    int cres=0;
    ll money=k;
    vector<pair<ll,ll>>opts;
    for(int i=0;i<n;i++){
        if(distx[i]+disty[i]==distx[y]){ // is on the path from x to y
            cres++;
            money-=min(distx[i],disty[i]);
            opts.emplace_back(max(distx[i],disty[i])-min(distx[i],disty[i]),1e18);
        }else{
            opts.emplace_back(min(distx[i],disty[i]),max(distx[i],disty[i])-min(distx[i],disty[i]));
        }
    }
    if(money<0)
        return 0;
    
    return cres+solve(opts,money);
}

int max_score(int N,int X,int Y,ll K,vector<int>U,vector<int>V,vector<int>W){
    n=N;
    x=X;
    y=Y;
    k=K;
    for(int i=0;i<n;i++){
        distx[i]=0;
        disty[i]=0;
        nodes[i].clear();
    }
    for(int i=0;i<n-1;i++){
        nodes[U[i]].emplace_back(V[i],W[i]);
        nodes[V[i]].emplace_back(U[i],W[i]);
    }
    dfs1(x,x,distx);
    dfs1(y,y,disty);
    
    return max(lvl1(),lvl2());
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 32192 KB Output is correct
2 Correct 78 ms 36812 KB Output is correct
3 Correct 42 ms 10068 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5144 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5020 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4960 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Correct 2 ms 5208 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5144 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5020 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4960 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Correct 2 ms 5208 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 4 ms 5208 KB Output is correct
26 Correct 36 ms 5732 KB Output is correct
27 Correct 3 ms 5720 KB Output is correct
28 Correct 17 ms 5784 KB Output is correct
29 Correct 29 ms 5980 KB Output is correct
30 Correct 3 ms 5468 KB Output is correct
31 Correct 3 ms 5700 KB Output is correct
32 Correct 3 ms 5468 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5144 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '21', found: '20'
20 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5144 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5020 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 4952 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 1 ms 4956 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 2 ms 4956 KB Output is correct
28 Correct 2 ms 4952 KB Output is correct
29 Correct 2 ms 4956 KB Output is correct
30 Correct 2 ms 4956 KB Output is correct
31 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '21', found: '20'
32 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5144 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5020 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4960 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 3 ms 5208 KB Output is correct
23 Correct 2 ms 5208 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 4 ms 5208 KB Output is correct
27 Correct 36 ms 5732 KB Output is correct
28 Correct 3 ms 5720 KB Output is correct
29 Correct 17 ms 5784 KB Output is correct
30 Correct 29 ms 5980 KB Output is correct
31 Correct 3 ms 5468 KB Output is correct
32 Correct 3 ms 5700 KB Output is correct
33 Correct 3 ms 5468 KB Output is correct
34 Correct 2 ms 4952 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4952 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 1 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 2 ms 4956 KB Output is correct
42 Correct 2 ms 4956 KB Output is correct
43 Correct 2 ms 4952 KB Output is correct
44 Correct 2 ms 4956 KB Output is correct
45 Correct 2 ms 4956 KB Output is correct
46 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '21', found: '20'
47 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5144 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5020 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4960 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 3 ms 5208 KB Output is correct
23 Correct 2 ms 5208 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 4 ms 5208 KB Output is correct
27 Correct 36 ms 5732 KB Output is correct
28 Correct 3 ms 5720 KB Output is correct
29 Correct 17 ms 5784 KB Output is correct
30 Correct 29 ms 5980 KB Output is correct
31 Correct 3 ms 5468 KB Output is correct
32 Correct 3 ms 5700 KB Output is correct
33 Correct 3 ms 5468 KB Output is correct
34 Correct 2 ms 4952 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4952 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 1 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 2 ms 4956 KB Output is correct
42 Correct 2 ms 4956 KB Output is correct
43 Correct 2 ms 4952 KB Output is correct
44 Correct 2 ms 4956 KB Output is correct
45 Correct 2 ms 4956 KB Output is correct
46 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '21', found: '20'
47 Halted 0 ms 0 KB -