제출 #716367

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

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PI 3.14159265
#define ll                  long long
#define pb                  push_back
#define pii                 pair<ll,ll>
#define vi                  vector<ll>
#define loop(i,a,b)         for(int i=(a);i<=(b);i++)
#define looprev(i,a,b)      for(int i=(a);i>=(b);i--)
#define all(v)              v.begin(),v.end()
#define ff                  first 
#define ss                  second
#define boost               ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define log(args...)        {string _s=#args;replace(_s.begin(),_s.end(),',',' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);err(_it,args);}
#define logarr(arr,a,b)     for(int z=(a);z<=(b);z++) cerr<<(arr[z])<<" ";cerr<<endl;
using namespace std;
using namespace __gnu_pbds;
void err(istream_iterator<string> it){}
template<typename T,typename... Args> 
void err(istream_iterator<string> it,T a,Args... args){
    cerr<<*it<<" = "<<a<<endl;
    err(++it,args...);
}
template<class T> void debug(set<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(multiset<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(unordered_set<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T,class X> void debug(T *arr,X s,X e){cerr<<"[ ";loop(i,s,e) cerr<<arr[i]<<" ";cerr<<"] "<<endl;}
template<class T,class V> void debug(pair<T,V> p){cerr<<"{";cerr<<p.ff<<" "<<p.ss<<"}"<<endl;}
template<class T,class V> void debug(vector<pair<T,V>> v){cerr<<"[ "<<endl;for(auto i:v) debug(i);cerr<<"]"<<endl;}
template<class T> void debug(vector<T> v){cerr<<"[ ";for(auto i:v) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(vector<vector<T>> v){cerr<<"[ "<<endl;for(auto i:v) debug(i);cerr<<"] "<<endl;}
// typedef tree<int, null_type, less<int>,
//             rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// vi primes(){
//     int N=3e6;
//     vi isPrime(N+5,1);
//     isPrime[0]=0;
//     isPrime[1]=0;
//     loop(i,2,N){
//         if(isPrime[i]==0) continue;
//         int z=2*i;
//         while(z<N){
//             isPrime[z]=0;
//             z+=i;
//         }
//     }
//     return isPrime;
// }
// vi *getfactors(){
//     int N=2e5;
//     vi *factors=new vi[N+5];
//     loop(i,1,N){
//         for(int j=i;j<=N;j+=i){
//             factors[j].pb(i);
//         }
//     }
//     // time complexity O(nlogn)
//     return factors;
// }
// const int mod=998244353;
// ll *getfactorial(){
//     int m=2e5;
//     ll *fact=new ll[m+1];
//     fact[0]=1;
//     loop(i,1,m){
//         fact[i]=(fact[i-1]*i)%mod;
//     }
//     // time complexity O(n)
//     return fact;
// }
// ll *fac;
// ll power(ll a,ll b,ll m=mod){
//     if(b==0) return 1;
//     if(b==1) return a;
//     ll ans=power(a,b/2);
//     ans=(1ll*ans*ans)%m;
//     if(b%2==1){
//         ans=(1ll*ans*a)%m;
//     }
//     return ans;
// }
// ll nCr(ll n,ll r,int m=mod){
//     if(n<r) return 0; 
//     ll ans=fac[n];
//     ans=(ans*power(fac[n-r],m-2))%m;
//     ans=(ans*power(fac[r],m-2))%m;
//     return ans;
// }
// int gcd(int a,int b){
//     if(b==0) return a;
//     if(a==0) return b;
//     return gcd(b,a%b);
// }
const int N=2e5+5;
ll n,k;
vector<pii> adjlst[N];
vi vis(N),sz(N);
map<ll,ll> mpp;
ll ans=1e18;
int dfs(int v,int p=-1){
    sz[v]=1;
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        ll w=temp.ss;
        if(i==p || vis[i]) continue;
        sz[v]+=dfs(i,v);
    }
    return sz[v];
}
int getC(int v,int p,int s){
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        ll w=temp.ss;
        if(i==p || vis[i]) continue;
        if(sz[i]*2>s) return getC(i,v,s);
    }
    return v;
}
void dfs2(int v,int p,ll w1,int depth){
    // if(w1>k) return ;
    if(mpp.find(k-w1)!=mpp.end()){
        ans=min(ans,depth+mpp[k-w1]);
    }
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        ll w=temp.ss;
        if(i==p || vis[i]) continue;
        dfs2(i,v,w1+w,depth+1);
    }
}
void dfs3(int v,int p,ll w1,int depth){
    // if(w1>k) return ;
    if(mpp.find(w1)==mpp.end()){
        mpp[w1]=depth;
    }
    else{
        if(mpp[w1]>depth){
            mpp[w1]=depth;
        }
    }
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        ll w=temp.ss;
        if(i==p || vis[i]) continue;
        dfs3(i,v,w1+w,depth+1);
    }    
}
void createTree(int v){
    int c=getC(v,-1,dfs(v));
    // log(c);
    vis[c]=1;
    mpp[0]=0;
    for(auto temp:adjlst[c]){
        int i=temp.ff;
        ll w=temp.ss;
        if(vis[i]){
            continue;
        }   
        // log(i);
        dfs2(i,c,w,1);
        dfs3(i,c,w,1);
    }
    mpp.clear();
    // log(ans);
    for(auto temp:adjlst[c]){
        int i=temp.ff;
        ll w=temp.ss;
        if(vis[i]) continue;
        createTree(i);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    n=N;
    k=K;
    loop(i,0,n-2){
        int c=L[i];
        int a=H[i][0],b=H[i][1];
        adjlst[a].pb({b,c});
        adjlst[b].pb({a,c});
    }
    createTree(0);
    if(ans!=1e18) return ans;
    else return -1;
}
// void test_case(){   
//     cin>>n>>k;
//     int H[n][2],L[n];
//     loop(i,0,n-2){
//         cin>>H[i][0]>>H[i][1];
//     }
//     loop(i,0,n-2){
//         cin>>L[i];
//     }
//     cout<<best_path(n,k,H,L)<<endl;
// }       
// int main(){
//     boost
//     int t=1;
//     // cin>>t;
//     while(t--){
//         test_case();
//     }  

// }

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

race.cpp: In function 'int dfs(int, int)':
race.cpp:105:12: warning: unused variable 'w' [-Wunused-variable]
  105 |         ll w=temp.ss;
      |            ^
race.cpp: In function 'int getC(int, int, int)':
race.cpp:114:12: warning: unused variable 'w' [-Wunused-variable]
  114 |         ll w=temp.ss;
      |            ^
race.cpp: In function 'void createTree(int)':
race.cpp:168:12: warning: unused variable 'w' [-Wunused-variable]
  168 |         ll w=temp.ss;
      |            ^

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