Submission #712659

#	Time	Username	Problem	Language	Result	Execution time	Memory
712659		Urvuk3	Race (IOI11_race)	C++17	0 / 100	1 ms	212 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 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<pii>> adj;
vector<bool> vis;
vector<int> siz;
vector<int> dub,dubw;
unordered_map<int,int> global,local;
int grana,W,res,T,H;

void DfsDecompose(int node,int par){
    siz[node]=1;
    for(pii e:adj[node]){
        if(!vis[e.fi] && e.fi!=par){
            DfsDecompose(e.fi,node);
            siz[node]+=siz[e.fi];
        }
    }
}

void Dfs(int node,int par,int w){
    if(par==-1){
        dub[node]=1;
        dubw[node]=0;
    }
    else{
        dub[node]=dub[par]+1;
        dubw[node]=dubw[par]+w;
    }
    T=dubw[node]+grana,H=dub[node];
    local[T]=min((local.count(T) ? local[T] : INF),H);
    res=min(res,local[T]+(global.count(W-T) ? global[W-T] : INF));
    global[T]=min((global.count(T) ? global[T] : INF),H+1);
    for(pii e:adj[node]){
        if(!vis[e.fi] && e.fi!=par){
            Dfs(e.fi,node,e.se);
        }
    }
}

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

int Find(int node){
    DfsDecompose(node,-1);
    node=Find(node,-1,siz[node]);
    return node;
}

void Decompose(int node){
    node=Find(node);
    vis[node]=true;
    //Debug(node);
    global.clear();
    for(pii e:adj[node]){
        if(!vis[e.fi]){
            local.clear();
            grana=e.se;
            Dfs(e.fi,-1,0);
            //Debug(e.fi,local,global);
        }
    }
    res=min(res,(global.count(W) ? global[W] : INF));
    for(pii e:adj[node]){
        if(!vis[e.fi]) Decompose(e.fi);
    }
}

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=INF;
    Decompose(0);
    return (res>=INF ? -1 : res-1);
}

/*
6 5
0 1 2
1 2 1
2 3 1
3 4 1
4 5 5
1
*/

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