oj.uz

Submission #1065167

# Submission time Handle Problem Language Result Execution time Memory
1065167 2024-08-19T02:16:00 Z LittleOrange Closing Time (IOI23_closing) C++17
8 / 100
 151 ms 34640 KB 
#include "closing.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 2e18;
struct line{
    ll i,w;
};
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    ll n = N;
    ll x = X;
    ll y = Y;
    ll k = K;
    vector<vector<line>> con(n);
    for(ll i = 0;i<n-1;i++){
        con[U[i]].push_back({V[i],W[i]});
        con[V[i]].push_back({U[i],W[i]});
    }
    vector<ll> dis1(n,big),dis2(n,big);
    {
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll v){
            if(dis1[i]>v){
                dis1[i] = v;
                for(auto [j,w] : con[i]){
                    dfs(j,v+w);
                }
            }
        };
        dfs(x,0);
    }
    {
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll v){
            if(dis2[i]>v){
                dis2[i] = v;
                for(auto [j,w] : con[i]){
                    dfs(j,v+w);
                }
            }
        };
        dfs(y,0);
    }
    ll l = 0, r = big;
    while(l<r){
        ll m = l+r+1>>1;
        ll sm = 0;
        for(ll i = 0;i<n;i++){
            ll mi = min(dis1[i],dis2[i]);
            ll mx = max(dis1[i],dis2[i]);
            if(m>=mx) sm+=mx;
            else if(m>=mi) sm+=mi;
        }
        if(sm>k) r = m-1;
        else l = m;
    }
    ll cur = 0, ans = 0;
    vector<ll> v;
    for(ll i = 0;i<n;i++){
        ll mi = min(dis1[i],dis2[i]);
        ll mx = max(dis1[i],dis2[i]);
        if (mx<=l){
            cur += mx;
            ans += 2;
        }else if (mi<=l){
            cur += mi;
            ans += 1;
            if (mx==l+1){
                v.push_back(mx-mi);
            }
        }else if(mi==l+1){
            v.push_back(mi);
        }
    }
    sort(v.begin(),v.end());
    for(ll i : v){
        if(cur+i<=k){
            ans += 1;
            cur += i;
        }
    }
    return 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:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         ll m = l+r+1>>1;
      |                ~~~^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 28496 KB Output is correct
2 Correct 151 ms 34640 KB Output is correct
3 Correct 65 ms 2896 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -