Submission #722721

#	Time	Username	Problem	Language	Result	Execution time	Memory
722721		ktkerem	Race (IOI11_race)	C++17	0 / 100	9 ms	14420 KiB

race

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
#include "race.h"
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;  
const ll limit = 1e12+7;
const ll sus = 2e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::vector<llll> adj[sus];
ll ddc = 0 , dd[sus] , vis[sus] , sub[sus] , ff;
std::map<ll , ll> mp[sus];
ll calsub(ll crt , ll prv){
  sub[crt] = 1; 
  vis[crt] = 1;
  for(auto j:adj[crt]){
    if(j.fi != prv && vis[j.fi] == 0){
      sub[crt]+=calsub(j.fi , crt);
    }
  }
  return sub[crt];
}
ll fndcent(ll crt , ll prv , ll prt){
  ll kd = (prt > ff?0:1);
  ll p = -1;
  for(auto j:adj[crt]){
    if(j.fi != prv && dd[j.fi] == 0){
      ll i = fndcent(j.fi , crt  , sub[crt] - sub[j.fi] + prt);
      if(p == -1){
        p = i;
      }
      if(sub[j.fi] > ff){
        kd =0;
      }
    }
  }
  if(kd){
    return crt;
  }
  return p;
}
void ctf(ll crt , ll prv , ll fpr , ll o , ll p){
  mp[p][fpr] = o;
  for(auto j:adj[crt]){
    if(j.fi != prv && dd[j.fi] == 0){
      ctf(j.fi , crt , fpr + j.sec , o+1 , p);
    }
  }
}
ll calans(ll crt ,ll k){
  ddc++;
  dd[crt] = 1;
  ll jj = 0;
  ll x = 0;
  for(auto j:adj[crt]){
    if(dd[j.fi]==0){
      mp[x].clear();
      x++;
    }
  }
  for(auto j:adj[crt]){
    if(dd[j.fi]==0){
      ctf(j.fi , crt , j.sec , 1 , jj++);      
    }
  }
  ll ns = limit;
  std::map<ll , ll> mpx;
  mpx[0] = 0;
  for(ll i = 0;x>i;i++){
    for(auto j:mp[i]){
      if(mpx[k-j.fi] != 0 || k - j.fi == 0){
        ns = std::min(mpx[k-j.fi] + j.sec , ns);
      }
    }
    for(auto j:mp[i]){
      if(j.fi == 0){
        //do nothing
      }
      else if(mpx[j.fi] == 0){
        mpx[j.fi] = j.sec;
      }
      else{
        mpx[j.fi] = std::min(j.sec , mpx[j.fi]);
      } 
    }
  }
  return ns;
}
int best_path(int n , int k , int h[][2] ,int cst[]){
  for(ll i = 0 ; n-1>i;i++){
    adj[h[i][0]].pb({h[i][1] , cst[i]});
    adj[h[i][1]].pb({h[i][0] , cst[i]});
  }
  ll ans = limit;
  ddc = 0;
  for(ll i = 0 ; n>=i;i++){
    dd[i] = 0;
  }
  while(n > ddc){
    for(ll i = 0;n>i;i++){
      if(vis[i] == 0){
        calsub(i , -1);
        ff = sub[i]/2;
        ll cento = fndcent(i , -1 , 0);
        ans = std::min(calans(cento , k) , ans);
      }
    } 
    for(ll i = 0;n>i;i++){
      vis[i] = dd[i];
      sub[i] = 0;
    }
  }
  if(ans == limit){
    return -1;
  }
  return ans;
}
/*void solve(){
  ll hkn[15][2];
  for(ll i = 0;2>i;i++){
    for(ll j = 0;2>j;j++){
      std::cin >> hkn[i][j];
    }
  }
  ll alcst[10] = {1 , 1};
  ll ots = best_path(3 , 3 , hkn , alcst);
  std::cout << ots << "\n";
  return;
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  #ifndef ONLINE_JUDGE
    freopen("in.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
  #endif
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}*/

Compilation message (stderr)

race.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

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