Submission #715569

#	Time	Username	Problem	Language	Result	Execution time	Memory
715569		Urvuk3	Race (IOI11_race)	C++17	100 / 100	1532 ms	57664 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#ifndef ONLINE_JUDGE
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
#endif

vector<vector<pll>> adj;
vector<bool> vis;
vector<ll> siz;
vector<ll> dub,dubw;
map<ll,ll> global,local;
ll res,W;

void DfsDecompose(int node,int par){
    siz[node]=1;
    for(pll p:adj[node]){
        int v=p.fi,w=p.se;
        if(!vis[v] && v!=par){
            DfsDecompose(v,node);
            siz[node]+=siz[v];
        }
    }
}

void Dfs(int node,int par,int wp){
    if(par==-1){
        dub[node]=1;
        dubw[node]=wp;
    }
    else{
        dub[node]=dub[par]+1;
        dubw[node]=dubw[par]+wp;
    }
    local[dubw[node]]=min((local.count(dubw[node]) ? local[dubw[node]] : INF),dub[node]);
    for(pll p:adj[node]){
        int v=p.fi,w=p.se;
        if(!vis[v] && v!=par){
            Dfs(v,node,w);
        }
    }
}

int Find(int node,int par,int n){
    for(pll p:adj[node]){
        int v=p.fi,w=p.se;
        if(!vis[v] && v!=par && siz[v]>n/2)
            return Find(v,node,n);
    }
    return node;
}

void Decompose(int node){
    DfsDecompose(node,-1);
    node=Find(node,-1,siz[node]);
    vis[node]=true;
    //Debug(node);
    global.clear();
    for(pll p:adj[node]){
        int v=p.fi,w=p.se;
        if(!vis[v]){
            local.clear();
            Dfs(v,-1,w);
            for(auto p:local){
                res=min(res,(global.count(W-p.fi) ? global[W-p.fi] : INF)+p.se);
            }
            for(auto p:local){
                global[p.fi]=min((global.count(p.fi) ? global[p.fi] : INF),p.se);
            }
            //Debug(v);
            //Debug(local);
        }
    }
    res=min(res,(global.count(W) ? global[W] : INF));
    for(pll p:adj[node]){
        int v=p.fi,w=p.se;
        if(!vis[v]) Decompose(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    adj.resize(N+1); siz.resize(N+1); vis.resize(N+1); dub.resize(N+1); dubw.resize(N+1);
    W=K;
    for(int i=0;i<N-1;i++){
        int u=H[i][0],v=H[i][1],w=L[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    res=LINF;
    Decompose(0);
    return (res>=INF ? -1 : res);
}

/*
4 3
0 1 1
1 2 2
1 3 4
2

3 3
0 1 1
1 2 1
-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
2
*/

Compilation message (stderr)

race.cpp: In function 'void DfsDecompose(int, int)':
race.cpp:68:20: warning: unused variable 'w' [-Wunused-variable]
   68 |         int v=p.fi,w=p.se;
      |                    ^
race.cpp: In function 'int Find(int, int, int)':
race.cpp:96:20: warning: unused variable 'w' [-Wunused-variable]
   96 |         int v=p.fi,w=p.se;
      |                    ^
race.cpp: In function 'void Decompose(int)':
race.cpp:126:20: warning: unused variable 'w' [-Wunused-variable]
  126 |         int v=p.fi,w=p.se;
      |                    ^

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