oj.uz

Submission #1099594

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

#define ternal asdasf


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

void DFS(long long u , long long 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];
        }
}

long long find_centroid(long long u , long long tree_sz , long long 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(long long u , long long par , long long h , long long len)
{
    if(ternal.find(h) == ternal.end())
        ternal[h] = len;
    else
        ternal[h] = min(ternal[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])
            solve(v.first , u  , h + v.second , len + 1);
}

void build_centroid(long long u)
{
    DFS(u , -1);
    long long 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: ternal)
            {
                if(global.find(x.first) == global.end())
                    global[x.first] = x.second;
                else
                    global[x.first] = min(global[x.first] , x.second);
            }
            ternal.clear();
        }
    global.clear();
    is_centroid[centroid] = true;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
            build_centroid(v.first);
}

long long best_path(int m , int p , int h[][2] , int l[])
{
    k = p;
    n = m;
    for(long long 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("centroid.INP","r",stdin);
////    freopen("BIEUTHUCNT.OUT","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cin >> n >> k;
//    for(long long i = 1 ; i <= n - 1 ; i++)
//    {
//        long long 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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 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 Incorrect 3 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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 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 Incorrect 3 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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 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 Incorrect 3 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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 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 Incorrect 3 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -