Submission #339176

#	Time	Username	Problem	Language	Result	Execution time	Memory
339176		bigDuck	Race (IOI11_race)	C++14	21 / 100	3095 ms	41964 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;
vector<pii> g[200010];
bool v[200010];
int res=1e9;







int subtask_2(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(subtask_2(u, l+d, h+1), res);
        }
    }
    v[s]=false;
    return res;
}










map<pii, int> h;
int sz[200010];

void build_sz(int s){
    v[s]=true;
    sz[s]=1;
    for(pii u:g[s]){
        if(!v[u.ft]){
            build_sz(u.ft);
            sz[s]+=sz[u.ft];
        }
    }
    v[s]=false;
    return;
}



pii find_centroids(int s, int total){
    v[s]=true;

            int mx=0, u=s;
        for(pii node:g[s]){

            if( (sz[node.ft]>mx) && (!v[node.ft]) ){
                mx=sz[node.ft];
                u=node.ft;
            }
            if( (v[node.ft]) && ( (total-sz[s])>mx ) ){
                mx=(total-sz[s]);
                u=node.ft;
            }
        }
    pii res;
     if(!v[u]){res=find_centroids(u, total);}
     else{
        res={u, s};
     }

    v[s]=false;
    return res;
}



multiset<pii> k1, k2;





void path(int s, int l, int h, int tp){

if(l>k){
    return;
}
if(tp==1){
    k1.insert({l, h});
}
else{
    k2.insert({l, h});
}
if(l==k){return;}

v[s]=true;

for(auto pr:g[s]){
    int u=pr.ft, d=pr.sc;
    if(!v[u]){
        path(u, l+d, h+1, tp);
    }
}

v[s]=false;
return;
}




void remove_edge(pii e, int d){
int u=e.ft, v=e.sc;
g[u].erase(find(g[u].begin(), g[u].end(),mp(v, d) ));
g[v].erase(find(g[v].begin(), g[v].end(),mp(u, d) ));
}



void combine(int d){

while((!k1.empty()) && (!k2.empty())){
    auto it1=k1.end(); it1--; int s1=it1->ft, pl1=it1->sc; k1.erase(it1);
    while( (((k2.begin()->ft)+s1)<(k-d)) && (!k2.empty()) ){
        k2.erase(k2.begin());
    }
    if(k2.empty()){
        break;
    }
    int s2=(*k2.begin()).ft, pl2=(*k2.begin()).sc;
    if( (s2+s1)==(k-d) ){
        res=min(res, pl1+pl2);
    }
}


}




void subtask_4(){
queue<int> forest;
forest.push(1);

while(!forest.empty()){
    int node=forest.front(); forest.pop();
    build_sz(node);

    //cout<<node<<"\n"<<flush;
    if(sz[node]==1){continue;}
    pii e=find_centroids(node, sz[node]);
    int d=h[e];
    //cout<<e.ft<<" "<<e.sc<<"\n"<<flush;

    //partea din stanga:
    k1.insert({0, 1});
    v[e.sc]=true;v[e.ft]=false;
    path(e.ft, 0, 1, 1); v[e.sc]=false;
    //partea din dreapta:
    k2.insert({0, 1});
    v[e.ft]=true; v[e.sc]=false;
    path(e.sc, 0, 1, 2); v[e.ft]=false;

    //combinarea:
    combine(d);
    k1.clear();
    k2.clear();

    remove_edge(e, d);
    forest.push(e.ft); forest.push(e.sc);
}


}








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].pb({v, d}); g[v].pb({u, d});
    h[{u, v} ]=d; h[{v, u} ]=d;
  }


    /*if( (k<=100) ){    subtask_3(1);}
    else{
        if(n<=1000){
        for(int i=1; i<=n; i++){
            res=min(res, subtask_2(i, 0, 1));
        }
        }
        else{
            subtask_4();
        }
    }*/
    subtask_4();
  if(res==(1e9)){
    return -1;
  }
  return res-1;
}

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