oj.uz

Submission #1099591

# Submission time Handle Problem Language Result Execution time Memory
1099591 2024-10-11T19:03:06 Z nhamtan Race (IOI11_race) C++17
0 / 100
 3 ms 4956 KB 
#include<bits/stdc++.h>
using namespace std;

#define internal asdasf


const int N = 2e5 + 5;
int n , k , ans = 1e9;
int sz[N];
bool is_centroid[N];
vector < pair < int , int > > g[N];
map < int , int > internal , global;

void DFS(int u , int par)
{
    sz[u] = 1;
    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first])
        {
            DFS(v.first , u);
            sz[u] += sz[v.first];
        }
}

int find_centroid(int u , int tree_sz , int par)
{
    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first] && sz[v.first] > tree_sz / 2)
            return find_centroid(v.first , tree_sz , u);
    return u;
}

void solve(int u , int par , int h , int len)
{
    if(internal.find(h) == internal.end())
        internal[h] = len;
    else
        internal[h] = min(internal[h] , len);

    if(global.find(k - h) != global.end())
        ans = min(ans , len + global[k - h]);

    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first] && (long long)h + v.second <= k)
            solve(v.first , u  , h + v.second , len + 1);
}

void build_centroid(int u)
{
    DFS(u , -1);
    int centroid = find_centroid(u , sz[u] , -1);
    global[0] = 0;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
        {
            solve(v.first , centroid , v.second , 1);
            for(auto x: internal)
            {
                if(global.find(x.first) == global.end())
                    global[x.first] = x.second;
                else
                    global[x.first] = min(global[x.first] , x.second);
            }
            internal.clear();
        }
    global.clear();
    is_centroid[centroid] = true;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
            build_centroid(v.first);
}

int best_path(int m , int p , int h[][2] , int l[])
{
    k = p;
    n = m;
    for(int i = 0 ; i <= n - 1 ; i++)
    {
        h[i][0]++;
        h[i][1]++;
        g[h[i][0]].push_back({h[i][1] , l[i]});
        g[h[i][1]].push_back({h[i][0] , l[i]});
    }
    build_centroid(1);
    if(ans == 1e9)
        return -1;
    else
        return ans;
}

//main()
//{
////    freopen("BIEUTHUCNT.INP","r",stdin);
////    freopen("BIEUTHUCNT.OUT","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cin >> n >> k;
//    for(int i = 1 ; i <= n - 1 ; i++)
//    {
//        int u , v , w;
//        cin >> u >> v >> w;
//        u++;v++;
//        g[u].push_back({v , w});
//        g[v].push_back({u , w});
//    }
//    build_centroid(1);
//    if(ans == 1e9)
//        cout << "-1";
//    else
//        cout << ans << "\n";
//}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -