oj.uz

Submission #1100279

# Submission time Handle Problem Language Result Execution time Memory
1100279 2024-10-13T11:52:10 Z kokoue Race (IOI11_race) C++14
0 / 100
 2 ms 10576 KB 
#include<bits/stdc++.h>
#include "race.h"
#define maxn 200010
#define maxk 1000010
#define f first
#define s second
#define ll long long
using namespace std;
int n,k;
int subsz[maxn],cnt[maxk];
bool is_cen[maxn];
int mx_sz=0;
int ans=INT_MAX;
vector<pair<int,int>> edges[maxn];
int get_size(int start,int parent=-1)
{
    int sz=1;
    for(auto e:edges[start])
    {
        if(e.f==parent || is_cen[e.f]) continue;
        sz+=get_size(e.f,start);
    }
    return subsz[start]=sz;
}
int find_centroid(int start,int tree_sz,int parent=-1)
{
    for(auto e:edges[start])
    {
        if(e.f==parent || is_cen[e.f]) continue;
        if(2*subsz[e.f]>tree_sz) return find_centroid(e.f,tree_sz,start);
    }
    return start;
}
void get_cnt(int start,bool filling,int parent,int dist,int depth=1)
{
    if(dist>k) return;
    mx_sz=max(mx_sz,dist);

    if(filling)
    {
        //cnt[depth]++;
        //if(cnt[dist]==INT_MAX) cnt[dist]
        cnt[dist]=min(cnt[dist],depth);
    }
    else if(cnt[k-dist]!=INT_MAX) ans=min(ans,cnt[k-dist]+depth);

    for(auto e:edges[start])
    {
        if(is_cen[e.f] || e.f==parent) continue;
        get_cnt(e.f,filling,start,dist+e.s,depth+1);
    }
}
void decomp(int start=1)
{
    int centroid=find_centroid(start,get_size(start));
    is_cen[centroid]=1;
    mx_sz=0;
    for(auto e:edges[centroid])
    {
        if(is_cen[e.f]) continue;
        get_cnt(e.f,false,centroid,e.s);
        get_cnt(e.f,true,centroid,e.s);
    }
    for(int i=1;i<=mx_sz;i++) cnt[i]=INT_MAX;
    for(auto e:edges[centroid])
    {
        if(is_cen[e.f]) continue;
        decomp(e.f);
    }
}
int best_path(int nn,int kk,int h[][2],int l[])
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;*/
    n=nn;
    k=kk;
    for(int i=1;i<=k;i++) cnt[i]=INT_MAX;
    for(int i=0;i<n-1;i++)
    {
        int a=h[i][0],b=h[i][0],w=l[i];
        //cin>>a>>b>>w;
        a++;
        b++;
        edges[a].push_back({b,w});
        edges[b].push_back({a,w});
    }
    decomp();
    if(ans!=INT_MAX) return ans;
    else return -1;
}
/*
3 3
0 1 1
1 2 1
*/
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10576 KB Output isn't correct
2 Halted 0 ms 0 KB -