제출 #716356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716356		sktime	Race (IOI11_race)	C++14	0 / 100	1 ms	596 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=2e3+5;
int n,k;
vector<pii> adjlst[N];
vi vis(N),sz(N);
int dfs(int v,int p=-1){
    sz[v]=1;
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        int 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;
        int w=temp.ss;
        if(i==p || vis[i]) continue;
        if(sz[i]*2>s) return getC(i,v,s);
    }
    return v;
}
map<ll,ll> mpp;
ll ans=1e18;
void dfs2(int v,int p,int 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;
        int w=temp.ss;
        if(i==p || vis[i]) continue;
        dfs2(i,v,w1+w,depth+1);
    }
}
void dfs3(int v,int p,int w1,int depth){
    if(w1>k) return ;
    if(mpp.find(w1)==mpp.end()){
        mpp[w1]=depth;
    }
    for(auto temp:adjlst[v]){
        int i=temp.ff;
        int w=temp.ss;
        if(i==p || vis[i]) continue;
        dfs2(i,v,w1+w,depth+1);
    }    
}
int createTree(int v){
    int c=getC(v,-1,dfs(v));
    // log(c);
    vis[c]=1;
    for(auto temp:adjlst[c]){
        int i=temp.ff;
        int w=temp.ss;
        if(vis[i]){
            continue;
        }   
        // log(i);
        dfs2(i,v,w,1);
        dfs3(i,v,w,1);
    }
    mpp.clear();
    // log(ans);
    for(auto temp:adjlst[c]){
        int i=temp.ff;
        int 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:103:13: warning: unused variable 'w' [-Wunused-variable]
  103 |         int w=temp.ss;
      |             ^
race.cpp: In function 'int getC(int, int, int)':
race.cpp:112:13: warning: unused variable 'w' [-Wunused-variable]
  112 |         int w=temp.ss;
      |             ^
race.cpp: In function 'int createTree(int)':
race.cpp:162:13: warning: unused variable 'w' [-Wunused-variable]
  162 |         int w=temp.ss;
      |             ^
race.cpp:166:1: warning: no return statement in function returning non-void [-Wreturn-type]
  166 | }
      | ^

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