Submission #934427

#	Time	Username	Problem	Language	Result	Execution time	Memory
934427		dosts	Race (IOI11_race)	C++17	21 / 100	3017 ms	21396 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) dist(it.first,node,dep+1,sm+it.second);
}
int ans = inf;
unordered_map<int,int> mp;
int n,k;
void decompose(int node) {
    int c = cent(node,node,szs(node,node));
    taken[c] = 1;
    mp[0] = 0;
    for (auto it : edges[c]) {
        if (taken[it.first]) continue;
        dist(it.first,c,1,it.second);
        for (auto itt : v) {
          if (mp.count(k-itt.first)) {
            ans = min(ans,itt.second+mp[k-itt.first]);
          }
        }
        for (auto itt : v) {
          if (mp.count(itt.first)) mp[itt.first] = min(mp[itt.first],itt.second);
          else mp[itt.first] = itt.second;
        }
        if (mp.count(k)) ans = min(ans,mp[k]);
        v.clear();
    }
    mp.clear();
    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[])
{
  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: 0 / 22
• Subtask 4: 0 / 57