oj.uz

Submission #716367

# Submission time Handle Problem Language Result Execution time Memory
716367 2023-03-29T18:55:14 Z sktime Race (IOI11_race) C++14
100 / 100
 1043 ms 47828 KB 
#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();
//     }  

// }

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 5 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 6 ms 8148 KB Output is correct
17 Correct 4 ms 8148 KB Output is correct
18 Correct 4 ms 8040 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 5 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 6 ms 8148 KB Output is correct
17 Correct 4 ms 8148 KB Output is correct
18 Correct 4 ms 8040 KB Output is correct
19 Correct 6 ms 8116 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 6 ms 8148 KB Output is correct
22 Correct 6 ms 8276 KB Output is correct
23 Correct 7 ms 8276 KB Output is correct
24 Correct 6 ms 8276 KB Output is correct
25 Correct 6 ms 8276 KB Output is correct
26 Correct 5 ms 8276 KB Output is correct
27 Correct 5 ms 8148 KB Output is correct
28 Correct 6 ms 8276 KB Output is correct
29 Correct 5 ms 8276 KB Output is correct
30 Correct 5 ms 8276 KB Output is correct
31 Correct 6 ms 8148 KB Output is correct
32 Correct 5 ms 8276 KB Output is correct
33 Correct 6 ms 8276 KB Output is correct
34 Correct 6 ms 8276 KB Output is correct
35 Correct 6 ms 8276 KB Output is correct
36 Correct 5 ms 8276 KB Output is correct
37 Correct 5 ms 8148 KB Output is correct
38 Correct 6 ms 8276 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 5 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 6 ms 8148 KB Output is correct
17 Correct 4 ms 8148 KB Output is correct
18 Correct 4 ms 8040 KB Output is correct
19 Correct 231 ms 14428 KB Output is correct
20 Correct 251 ms 14424 KB Output is correct
21 Correct 271 ms 14308 KB Output is correct
22 Correct 206 ms 15836 KB Output is correct
23 Correct 286 ms 16292 KB Output is correct
24 Correct 126 ms 15472 KB Output is correct
25 Correct 213 ms 20360 KB Output is correct
26 Correct 102 ms 21620 KB Output is correct
27 Correct 280 ms 24404 KB Output is correct
28 Correct 978 ms 47828 KB Output is correct
29 Correct 973 ms 46928 KB Output is correct
30 Correct 287 ms 24452 KB Output is correct
31 Correct 281 ms 24240 KB Output is correct
32 Correct 381 ms 24328 KB Output is correct
33 Correct 473 ms 23140 KB Output is correct
34 Correct 893 ms 36280 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 5 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 6 ms 8148 KB Output is correct
17 Correct 4 ms 8148 KB Output is correct
18 Correct 4 ms 8040 KB Output is correct
19 Correct 6 ms 8116 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 6 ms 8148 KB Output is correct
22 Correct 6 ms 8276 KB Output is correct
23 Correct 7 ms 8276 KB Output is correct
24 Correct 6 ms 8276 KB Output is correct
25 Correct 6 ms 8276 KB Output is correct
26 Correct 5 ms 8276 KB Output is correct
27 Correct 5 ms 8148 KB Output is correct
28 Correct 6 ms 8276 KB Output is correct
29 Correct 5 ms 8276 KB Output is correct
30 Correct 5 ms 8276 KB Output is correct
31 Correct 6 ms 8148 KB Output is correct
32 Correct 5 ms 8276 KB Output is correct
33 Correct 6 ms 8276 KB Output is correct
34 Correct 6 ms 8276 KB Output is correct
35 Correct 6 ms 8276 KB Output is correct
36 Correct 5 ms 8276 KB Output is correct
37 Correct 5 ms 8148 KB Output is correct
38 Correct 6 ms 8276 KB Output is correct
39 Correct 231 ms 14428 KB Output is correct
40 Correct 251 ms 14424 KB Output is correct
41 Correct 271 ms 14308 KB Output is correct
42 Correct 206 ms 15836 KB Output is correct
43 Correct 286 ms 16292 KB Output is correct
44 Correct 126 ms 15472 KB Output is correct
45 Correct 213 ms 20360 KB Output is correct
46 Correct 102 ms 21620 KB Output is correct
47 Correct 280 ms 24404 KB Output is correct
48 Correct 978 ms 47828 KB Output is correct
49 Correct 973 ms 46928 KB Output is correct
50 Correct 287 ms 24452 KB Output is correct
51 Correct 281 ms 24240 KB Output is correct
52 Correct 381 ms 24328 KB Output is correct
53 Correct 473 ms 23140 KB Output is correct
54 Correct 893 ms 36280 KB Output is correct
55 Correct 23 ms 9172 KB Output is correct
56 Correct 16 ms 8908 KB Output is correct
57 Correct 127 ms 16132 KB Output is correct
58 Correct 43 ms 15036 KB Output is correct
59 Correct 324 ms 26316 KB Output is correct
60 Correct 1000 ms 46168 KB Output is correct
61 Correct 344 ms 26148 KB Output is correct
62 Correct 287 ms 24356 KB Output is correct
63 Correct 366 ms 24544 KB Output is correct
64 Correct 1043 ms 30236 KB Output is correct
65 Correct 1027 ms 37036 KB Output is correct
66 Correct 992 ms 45056 KB Output is correct
67 Correct 134 ms 23276 KB Output is correct
68 Correct 581 ms 34980 KB Output is correct
69 Correct 486 ms 34884 KB Output is correct
70 Correct 489 ms 33716 KB Output is correct