Submission #866342

#	Time	Username	Problem	Language	Result	Execution time	Memory
866342		yeediot	Race (IOI11_race)	C++17	100 / 100	327 ms	71588 KiB

race

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<long long,long long>
#define pb push_back
#define sz(x) (long long)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<long long>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
void setIO(string s) {
    freopen((s).c_str(), "r", stdin);
    //freopen((s + ".ou).c_str(), "w", stdout);
}
const long long mxn=1e6+5;
vector<pii>adj[mxn];
long long cnt[mxn];
bool vis[mxn];
int n,k;
void cnt_sz(long long v,long long pa){
    //cout<<v<<' ';
    cnt[v]=1;
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        cnt_sz(u,v);
        //cout<<u<<' ';
        cnt[v]+=cnt[u];
    }
}
long long find(long long v,long long pa,long long tar){
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        if(cnt[u]*2>tar)return find(u,v,tar);
    }
    return v;
}
long long ans=1e9;
vector<pii>dis;
void dfs(long long v,long long pa,long long l,long long len){
    if(len>k)return;
    dis.pb({l,len});
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        dfs(u,v,l+1,len+d);
    }
}
long long f[mxn];
void cd(long long v){
    cnt_sz(v,v);
    v=find(v,v,cnt[v]);
    vis[v]=1;
    f[0]=0;
    vector<long long>undo;
    for(auto [u,d]:adj[v]){
        if(vis[u])continue;
        dis.clear();
        dis.pb({0,0});
        dfs(u,v,1,d);
        for(long long j=0;j<sz(dis);j++){
            //cout<<dis[j].F<<' '<<dis[j].S<<'\n';
            chmin(ans,f[k-dis[j].S]+dis[j].F);
           // cout<<u<<' '<<dis[j].S<<' '<<dis[j].F<<' '<<f[k-dis[j].S]<<' '<<ans<<'\n';
        }
        for(long long j=0;j<sz(dis);j++){
            undo.pb(dis[j].S);
            chmin(f[dis[j].S],dis[j].F);
        }
    }
    for(auto x:undo)f[x]=1e9;
    for(auto [u,d]:adj[v]){
        if(vis[u])continue;
        cd(u);
    }
}
int best_path(int N,int K,int H[][2],int L[]){
    n=N;
    k=K;
    for(long long i=0;i<N-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    for(long long i=1;i<=K;i++){
        f[i]=1e9;
    }
    cd(0);
    return (ans>=1e9?-1:ans);
}
//signed main(){
//    setIO("/Users/iantsai/Downloads/ioi2011tests/race-test/subtask1/grader.in.1");
//    ios::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
//    int n,k;
//    cin>>n>>k;
//    int h[n-1][2];
//    int l[n-1];
//    for(long long i=0;i<n-1;i++){
//        cin>>h[i][0]>>h[i][1];
//        cin>>l[i];
//    }
//    for(long long i=0;i<n-1;i++){
//    }
//    cout<<best_path(n,k,h,l);
//}
 /*
 input:
  11 12
  0 1
  0 2
  2 3
  3 4
  4 5
  0 6
  6 7
  6 8
  8 9
  8 10
  3
  4
  5
  4
  6
  3
  2
  5
  6
  7
*/

Compilation message (stderr)

race.cpp: In function 'void setIO(std::string)':
race.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s).c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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