Submission #934445

#	Time	Username	Problem	Language	Result	Execution time	Memory
934445		dosts	Race (IOI11_race)	C++17	100 / 100	341 ms	49120 KiB

race

#pragma GCC optimize("O3,unroll-loops")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int LIM = 2e5+1,inf = 2e18;

vector<pii> edges[LIM]; 
vi sz(LIM),taken(LIM,0);

int szs(int node,int p) {
    sz[node] = 1;
    for (auto it : edges[node]) {
        if (it.first == p || taken[it.first]) continue;
        sz[node]+=szs(it.first,node);
    }
    return sz[node]; 
}

int cent(int node,int p,int x) {
    for (auto it : edges[node]) {
        if (taken[it.first] || it.first == p) continue;
        if (sz[it.first]*2 > x) return cent(it.first,node,x);
    }
    return node;
}

vector<pii> v;

void dist(int node,int p, int dep,int sm) {
    v.push_back({sm,dep});
    for (auto it : edges[node]) if (it.first != p && !taken[it.first]) dist(it.first,node,dep+1,sm+it.second);
}
int ans = inf;
int mp[1000001];
int n,k;
void decompose(int node) {
    int c = cent(node,node,szs(node,node));
    taken[c] = 1;
    mp[0] = 0;
    vi seen;
    for (auto it : edges[c]) {
        if (taken[it.first]) continue;
        dist(it.first,c,1,it.second);
        for (auto itt : v) {
          if (itt.first > k) continue;
          ans = min(ans,itt.second+mp[k-itt.first]);
        }
        for (auto itt : v) {
          if (itt.first > k) continue;
          seen.push_back(itt.first);
          mp[itt.first] = min(mp[itt.first],itt.second);
        }
        ans = min(ans,mp[k]);
        v.clear();
    }
    for (auto it : seen) mp[it] = inf;
    for (auto it : edges[c]) if (!taken[it.first]) decompose(it.first);
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
  for (int i=0;i<=K;i++) mp[i] = inf;
  n = N,k = K;
  for (int i=0;i<n-1;i++) {
    edges[H[i][0]+1].push_back({H[i][1]+1,L[i]});
    edges[H[i][1]+1].push_back({H[i][0]+1,L[i]});
  }
  decompose(1);
  return ans == inf?-1:ans;
}

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