제출 #441261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441261		julian33	경주 (Race) (IOI11_race)	C++14	100 / 100	693 ms	34992 KiB

race

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}

const int mxN=2e5+5,mxK=1e6+5;

vector<pll> graph[mxN];
int seen[mxN],sub[mxN],ans=1e9,K,N;
int mp[mxK];
vector<int> path;

int dfs(int at,int p){
    sub[at]=1;
    for(pll &u:graph[at]){
        int i=u.first; int w=u.second;
        if(i==p || seen[i])
            continue;
        sub[at]+=dfs(i,at);
    }
    return sub[at];
}

int centroid(int at,int p,int s){
    for(pll &u:graph[at]){
        int i=u.first; int w=u.second;
        if(i==p || seen[i])
            continue;
        if(2*sub[i]>=s)
            return centroid(i,at,s);
    }
    return at;
}

void solve(int at,int p,ll len,int filling,int h){
    if(len>K)
        return;
    if(filling){
        path.pb(len);
        mina(mp[len],h);
    } else{
        mina(ans,mp[K-len]+h);
    }
    for(pll &u:graph[at]){
        int i=u.first; int w=u.second;
        if(i==p || seen[i])
            continue;
        solve(i,at,len+w,filling,h+1);
    }
}

void build(int at){
    int s=dfs(at,-1);
    int cent=centroid(at,-1,s);
    mp[0]=0;
    for(pll &u:graph[cent]){
        int i=u.first; int w=u.second;
        if(!seen[i]){
            solve(i,cent,w,0,1);
            solve(i,cent,w,1,1);
        }
    }
    while(sz(path)){
        mp[path.back()]=1e9;
        path.pop_back();
    }
    seen[cent]=1;
    for(pll &u:graph[cent]){
        int i=u.first; int w=u.second;
        if(!seen[i])
            build(i);
    }
}

int best_path(int n,int k,int h[][2],int l[]){
    N=n; K=k;
    for(int i=0;i<n-1;i++){
        graph[h[i][0]].pb({h[i][1],l[i]});
        graph[h[i][1]].pb({h[i][0],l[i]});
    }
    fill(mp,mp+K+1,1e9);
    build(0);
    return ans==1e9?-1:ans;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int dfs(int, int)':
race.cpp:38:28: warning: unused variable 'w' [-Wunused-variable]
   38 |         int i=u.first; int w=u.second;
      |                            ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:48:28: warning: unused variable 'w' [-Wunused-variable]
   48 |         int i=u.first; int w=u.second;
      |                            ^
race.cpp: In function 'void build(int)':
race.cpp:91:28: warning: unused variable 'w' [-Wunused-variable]
   91 |         int i=u.first; int w=u.second;
      |                            ^

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