Submission #895169

#	Time	Username	Problem	Language	Result	Execution time	Memory
895169		anton	Race (IOI11_race)	C++17	100 / 100	363 ms	68704 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pll pair<ll,ll>
const ll INF = 1e18;

struct VSet{
  map<ll, ll> us;
  ll d= 0;
  ll d2 = 0;

  bool is_in(ll v){
    return (us.find(v-d)!=us.end());
  }

  ll min_len(ll v){
    auto it =us.find(v-d);
    if(it!=us.end()){
      //cout<<it->second + d2<<endl;
      return it->second + d2;
    }
    else{
      return INF;
    }
  }

  void add(pll v){
    //cout<<"adding "<<v.first<<" "<<v.second<<endl;
    if(min_len(v.first)>v.second){
      us[v.first-d] = v.second-d2;
      //cout<<"passed "<<us[v.first-d]<<endl;
    }
  }

  void display(){
    for(auto e: us){
      //cout<<e.first+d<<" "<<e.second+d2<<endl;
    }
    //cout<<endl;
  }
};

ll res= INF;
int k;

void merge(VSet& a, VSet& b){
  if(a.us.size()<b.us.size()){
    swap(a.us,b.us);
    swap(a.d, b.d);
    swap(a.d2, b.d2);
  }

  for(auto e: b.us){
    res = min(res, e.second +b.d2 + a.min_len(k-(e.first+b.d)));
  }

  for(auto e: b.us){
    a.add(pll(e.first+b.d, e.second + b.d2));
  }

  //cout<<"a size "<<a.us.size()<<endl;
}

vector<vector<pll>> ch;

VSet dfs(int u, int anc){
  VSet cur;
  cur.add(pll(0, 0));
  for(auto e: ch[u]){
    if(e.first!=anc){
      VSet rh = dfs(e.first, u);
      rh.d += e.second;
      rh.d2 ++;

      merge(cur, rh);
    }
  }
  //cout<<"dfs "<<u<<endl;
  cur.display();
  return cur;
}

int best_path(int N, int K, int H[][2], int L[])
{
  ch.resize(N);
  k = K;
  for(int i = 0; i<N-1; i++){
    ch[H[i][0]].push_back(pll(H[i][1], L[i]));
    ch[H[i][1]].push_back(pll(H[i][0], L[i]));
  }

  dfs(0, -1);

  if(res==INF){
    return -1;
  }
  return res;
}

Compilation message (stderr)

race.cpp: In member function 'void VSet::display()':
race.cpp:38:14: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   38 |     for(auto e: us){
      |              ^

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