Submission #920012

#TimeUsernameProblemLanguageResultExecution timeMemory
920012thunoproRace (IOI11_race)C++14
0 / 100
15 ms29528 KiB
#include<bits/stdc++.h> using namespace std ; #define maxn 200009 #define ll long long #define fi first #define se second #define pb push_back #define left id<<1 #define right id<<1|1 #define re exit(0); const int mod = 1e9+7; const int INF = 1e9; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vii; typedef vector<ll> vl; void add ( int &a , int b ) { a += b ; if ( a > mod ) a -= mod ; if ( a < 0 ) a += mod ; } template <typename T> void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } template <typename T> void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } int _pow ( int a , int n ) { if ( n == 0 ) return 1 ; int res = _pow (a,n/2) ; if ( n % 2 ) return 1ll*res*res%mod*a%mod ; else return 1ll*res*res%mod ; } void rf () { freopen ("bai1.inp","r",stdin) ; } const int maxm = 1e6+9 ; int n , k ; int h [maxn][2] , l [maxn] ; int res = INF ; vii adjList [maxn] ; int sz [maxn] , cnt [maxm] ; bool vis [maxn] ; int dfs_sz ( int u , int par ) { sz [u] = 1 ; for ( auto x : adjList [u] ) { int v = x.fi ; if ( v == par || vis [v] ) continue ; sz [u] += dfs_sz (v,u) ; } return sz [u] ; } int find_centroid ( int u , int par , int n ) { for ( auto x : adjList [u] ) { int v = x.fi ; if ( v == par || vis [v] ) continue ; if ( sz [v]*2 > n ) return find_centroid (v,u,n) ; } return u ; } void dfs1 ( int u , int par , int dep , int len ) { if ( len > k ) return ; chkmin (res,dep+cnt[k-len]) ; for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( v == par || vis [v] ) continue ; dfs1 (v,u,dep+1,len+w) ; } } void dfs2 ( int u , int par , int dep , int len ) { if ( len > k ) return ; chkmin (cnt[len],dep) ; for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( v == par || vis [v] ) continue ; dfs2 (v,u,dep+1,len+w) ; } } void dfs3 ( int u , int par , int dep , int len ) { cnt [len] = INF ; for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( v == par || vis [v] ) continue ; dfs3 (v,u,dep+1,len+w) ; } } void solve ( int u ) { int n = dfs_sz (u,-1) ; u = find_centroid (u,-1,n) ; cnt [0] = 0 ; for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( vis [v] ) continue ; dfs1 (v,u,1,w) ; dfs2 (v,u,1,w) ; } for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( vis [v] ) continue ; dfs3 (v,u,1,w) ; } vis [u] = true ; for ( auto x : adjList [u] ) { int v = x.fi , w = x.se ; if ( vis [v] ) continue ; solve (v) ; } } int best_path ( int N , int K , int H[][2] , int L[] ) { n = N , k = K ; for ( int i = 0 ; i < n-1 ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) h [i][j] = H [i][j] ; for ( int i = 0 ; i < n-1; i ++ ) l [i] = L [i] ; for ( int i = 0 ; i < n-1 ; i ++ ) { int u = h [i][0] , v = h [i][1] ; adjList [u] . pb ({v,l[i]}) ; adjList [v] . pb ({u,l[i]}) ; } memset (cnt,0x3f,sizeof cnt) ; solve (0) ; if ( res == INF ) res = - 1 ; return res ; } //int main () //{ // ios_base::sync_with_stdio(0); // cin.tie(0);cout.tie(0); // rf () ; // cin >> n >> k ; // for ( int i = 1 ; i < n ; i ++ ) for ( int j = 0 ; j < 2 ; j ++ ) cin >> h [i][j] ; // for ( int i = 1 ; i < n ; i ++ ) cin >> l [i] ; // cout << best_path (n,k,h,l) ; //}

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:129:18: warning: unused variable 'w' [-Wunused-variable]
  129 |   int v = x.fi , w = x.se ;
      |                  ^
race.cpp: In function 'void rf()':
race.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...