Submission #393388

#	Time	Username	Problem	Language	Result	Execution time	Memory
393388		juggernaut	Race (IOI11_race)	C++14	100 / 100	543 ms	34220 KiB

race

//Ураа .Я наконец-то понял центроид. 
#include"race.h"
#include<bits/stdc++.h>
#ifdef IOI2021SG
#include"grader.cpp"
#endif
using namespace std;
#define fr first
#define sc second
vector<pair<int,int>>g[200005];
const int INF=2e9;
int k,ans=INF;
int sz[200005];
bool vis[200005];
pair<int,int>mt[1000005];
int timer;
void calc_sz(int v,int p){
    sz[v]=1;
    for(auto to:g[v])if(to.fr!=p&&!vis[to.fr]){
        calc_sz(to.fr,v);
        sz[v]+=sz[to.fr];
    }
}
int centroid(int v,int p,int num){
    for(auto to:g[v])if(to.fr!=p&&!vis[to.fr])
        if(sz[to.fr]>num)return centroid(to.fr,v,num);
    return v;
}
void go(int v,int p,int depth,int weight){
    if(weight>k)return;
    if(mt[k-weight].fr==timer)
        ans=min(ans,depth+mt[k-weight].sc);
    for(auto to:g[v])if(to.fr!=p&&!vis[to.fr])go(to.fr,v,depth+1,weight+to.sc);
}
void update(int v,int p,int depth,int weight){
    if(weight>k)return;
    if(mt[weight].fr==timer)mt[weight].sc=min(mt[weight].sc,depth);
    else mt[weight]={timer,depth};
    for(auto to:g[v])if(to.fr!=p&&!vis[to.fr])update(to.fr,v,depth+1,weight+to.sc);
}
void decompose(int v){
    calc_sz(v,v);
    v=centroid(v,v,sz[v]>>1);
    timer++;
    mt[0]={timer,0};
    for(auto to:g[v]){
      if(vis[to.fr])continue;
        go(to.fr,v,1,to.sc);
        update(to.fr,v,1,to.sc);
    }
    vis[v]=true;
    for(auto to:g[v])if(!vis[to.fr])decompose(to.fr);
}
int best_path(int n,int K,int h[][2],int l[]){
    k=K;
    for(int i=1;i^n;i++){
        g[h[i-1][1]].push_back({h[i-1][0],l[i-1]});
        g[h[i-1][0]].push_back({h[i-1][1],l[i-1]});
    }
    decompose(0);
    if(ans==INF)return -1;
    return ans;
}
/*
3 3
0 1 1
1 2 1
-1
 
 
 
 
4 3
0 1 1
1 2 2
1 3 4
2
 
 
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
2
 
 
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57