Submission #339915

#	Time	Username	Problem	Language	Result	Execution time	Memory
339915		bigDuck	Race (IOI11_race)	C++14	21 / 100	3078 ms	20460 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int n, k;
set<pii> g[200010];
bool v[200010];
int res=1e9;


int sz[200010];

void build_sz(int s){
    v[s]=true;
    sz[s]=1;
    for(auto u:g[s]){

        if(!v[u.ft]){
            build_sz(u.ft);
            sz[s]+=sz[u.ft];
        }
    }
    v[s]=false;
    return;
}


int c, mx;
void find_centroid(int s, int total){
    v[s]=true;
    int ac=max(sz[s], total-sz[s]+1);
    if(ac<mx){
        c=s; mx=ac;
    }

    int nxt=0, sm=0;
    for(pii e:g[s]){
        int u=e.ft;
        if(!v[u]){find_centroid(u, total);}
    }
    v[s]=false;
}



int k1[1000010];


vector<pii> rec;
vector<pii> del;


queue<int> forest;
void path(int s, int l, int h, int c){

v[s]=true;


if((k1[k-l]>0) ){
    res=min(res, h+k1[k-l]-1);
}

for(auto pr:g[s]){

    int u=pr.ft, d=pr.sc;

    if( (!v[u]) && ( (l+d)<=(k) ) ){
        path(u, l+d, h+1, c);
        if(s==c){
            while(!rec.empty()){
                del.pb(rec.back());
                if(k1[rec.back().ft]==0){
                    k1[rec.back().ft]=rec.back().sc;
                }
                else{
                    k1[rec.back().ft]=min(k1[rec.back().ft], rec.back().sc);
                }
                rec.pop_back();
            }
        }
    }
}

rec.pb({l, h});

v[s]=false;
if(s==c){
    while(!del.empty()){
        k1[del.back().ft]=0;
        del.pop_back();
    }
    rec.clear(); del.clear();
}


return ;
}










void subtask_4(){

forest.push(1);

while(!forest.empty()){
    int node=forest.front(); forest.pop();
    build_sz(node);
    if(sz[node]==1){continue;}
    mx=1e18;
    find_centroid(node, sz[node]);
    //cout<<c<<"\n"<<flush;
    k1[0]=1;
    path(c, 0, 1, c);
    for(auto pr:g[c]){
            int u=pr.ft, d=pr.sc;
            g[u].erase({c, d});
            forest.push(u);
    }
    g[c].clear();
}


}




int dfs2(int s, int l, int h){
int res=1e9;
    if(l>k){
            v[s]=false;
        return res;
    }
    if(l==k){
            v[s]=false;
        return h;
    }
    v[s]=true;
    for(pii pr:g[s]){
        int u=pr.ft, d=pr.sc;
        if(!v[u]){
            res=min(dfs2(u, l+d, h+1), res);
        }
    }
    v[s]=false;
    return res;
}










int best_path(int N, int K, int H[][2], int L[])
{
  n=N; k=K;

  for(int i=0; i<(n-1); i++){
    int u=H[i][0]+1, v=H[i][1]+1, d=L[i];
    g[u].insert({v, d}); g[v].insert({u, d});
  }


    for(int i=1; i<=n; i++){
        res=min(res, dfs2(i, 0, 1));
    }
  if(res==(1e9)){
    return -1;
  }
  return res-1;
}

Compilation message (stderr)

race.cpp: In function 'void find_centroid(int, int)':
race.cpp:44:9: warning: unused variable 'nxt' [-Wunused-variable]
   44 |     int nxt=0, sm=0;
      |         ^~~
race.cpp:44:16: warning: unused variable 'sm' [-Wunused-variable]
   44 |     int nxt=0, sm=0;
      |                ^~
race.cpp: In function 'void subtask_4()':
race.cpp:124:8: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  124 |     mx=1e18;
      |        ^~~~

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