Submission #1286043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286043		dssfsuper2	경주 (Race) (IOI11_race)	C++20	21 / 100	3090 ms	22616 KiB

race

#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
vector<vector<pii>> graph;
bitset<200010> deactivated;
vector<long long> sts;
long long getsts(long long node, long long parent=-1){
  sts[node]=1;
  for(auto thing:graph[node]){
    if(thing.first!=parent && !deactivated[thing.first])sts[node]+=getsts(thing.first, node);
  }
  return sts[node];
}
long long getcentroid(long long node, long long parent, long long tsize){
  for(auto thing:graph[node]){
    if(!deactivated[thing.first] && thing.first!=parent){
      if(sts[thing.first]*2>tsize)return getcentroid(thing.first, node, tsize);
    }
  }
  return node;
}
vector<pii> getpth(long long node, long long parent, long long ch, long long depth=0){
  vector<pii> can;
  can.push_back({ch, depth});
  for(auto thing:graph[node]){
    if(!deactivated[thing.first]&&thing.first!=parent){
      vector<pii> thm=getpth(thing.first, node, ch+thing.second, depth+1);
      for(auto thing:thm){
        can.push_back(thing);
      }
    }
  }
  return can;
}
long long fres=1e9;
long long gk;
void calcmain(long long node){
  long long res =0;
  long long tsize=getsts(node);
  long long curcen=getcentroid(node, -1, tsize);
  //cerr << node << " a "  << curcen << '\n';
  //if(node==6)cerr<< sts[node] << ' ' << sts[8] << ' '<< sts[7] << ' ' << deactivated[0] << '\n';
  long long cc=0;
  map<long long, pair<pii, pii>> mc;
  mc[0]={{0, 0}, {0, 0}};
  vector<vector<long long>> total={{0, 0, 0}};
  //i need a pair from different subtrees with the needed sum, 
  for(auto thing:graph[curcen]){
    if(!deactivated[thing.first]){
      cc++;
      auto s = getpth(thing.first, curcen, thing.second, 1);
      for(auto thing:s){
        total.push_back({cc, thing.first, thing.second});
        if(mc[thing.first].first.first==0 || mc[thing.first].first.first>thing.second)mc[thing.first].first={thing.second, cc};
      }
    }
  }
  for(auto thing:total){
    if(thing[0]!=mc[thing[1]].first.second && (mc[thing[1]].second.first==0 || mc[thing[1]].second.first>thing[2]))mc[thing[1]].second={thing[2], thing[0]};
  }
  for(auto thing:total){
    //cerr << node << ' ' << thing.first << ' ' << thing.second.first.first << ' ' << thing.second.first.second << ' ' << thing.second.second.first << ' ' << thing.second.second.second << '\n'; 
    long long clen=gk-thing[1];
    pii cf=mc[clen].first;
    if(cf.first==0)continue;
    pii cs=mc[clen].second;
    if(cf.second==thing[0]){
      if(cs.first==0)continue;
      fres=min(fres, cs.first+thing[2]);
      //cerr << node << ' ' << cs.first << ' ' << thing[2] << '\n';
    }
    else{
      fres=min(fres, cf.first+thing[2]);
      //cerr << node <<' ' <<  cf.first << ' ' << thing[2] << '\n';
    }
  }
  //cerr << node << ' ' << fres << '\n';
  deactivated[curcen]=1;
  for(auto thing:graph[curcen]){
    if(!deactivated[thing.first])calcmain(thing.first);
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  gk=K;
  sts.resize(N+1);
  graph.resize(N+1);
  for(int i = 0;i<N-1;i++){
    graph[H[i][0]].push_back({H[i][1], L[i]});
    graph[H[i][1]].push_back({H[i][0], L[i]});
  }
  calcmain(0);
  if(fres==1e9)return -1;
  return fres;
}

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