Submission #829744

#	Time	Username	Problem	Language	Result	Execution time	Memory
829744		Dec0Dedd	Race (IOI11_race)	C++14	9 / 100	3052 ms	15596 KiB

race

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 2e5+10;
const int K = 1e6+100;
const int INF = 1e9+10;

int n, k, sub[N], mn[K+10];
vector<pii> G[N];
bool rm[N];

void pre(int v, int p) {
    sub[v]=1;
    for (auto u : G[v]) {
        if (u.first == p || rm[u.first]) continue;
        pre(u.first, v);
        sub[v]+=sub[u.first];
    }
}

int cent(int v, int p, int sz) {
    int x=v; bool ok=2*(sz-sub[v]) <= sz;
    for (auto u : G[v]) {
        if (u.first == p || rm[u.first]) continue;

        int r=cent(u.first, v, sz);
        if (sub[u.first]*2 > sz) ok=false;
        if (r > -1) x=r;
    }

    if (ok) x=v;
    return x;
}

int add(int v, int p, int dt, ll s) {
    int res=INF;
    if (s <= k) res=min(res, dt+mn[k-s]);
    for (auto u : G[v]) {
        if (u.first == p || rm[u.first]) continue;
        res=min(res, add(u.first, v, dt+1, s+u.second));
    }
    if (s <= k) mn[s]=min(mn[s], dt);
    return res;
}

void rem(int v, int p, ll s) {
    if (s <= k) mn[s]=INF;
    for (auto u : G[v]) {
        if (u.first == p || rm[u.first]) continue;
        rem(u.first, v, s+u.second);
    }
}

int solve(int v) {
    pre(v, v); int sz=sub[v];
    int r=cent(v, v, sz);

    int ans=INF; rm[r]=true;
    for (auto u : G[r]) {
        if (rm[u.first]) continue;
        ans=min(ans, add(u.first, r, 1, u.second));
        ans=min(ans, mn[k]);
    }

    for (auto u : G[r]) {
        if (rm[u.first]) continue;
        rem(u.first, r, u.second);
    }

    for (auto u : G[r]) {
        if (rm[u.first]) continue;
        ans=min(ans, solve(u.first));
    } return ans;
}

int best_path(int sz, int l, int h[][2], int w[]) {
    n=sz, k=l;

    for (int i=0; i<=K; ++i) mn[i]=INF;
    for (int i=0; i<n-1; ++i) {
        int a=h[i][0]+1, b=h[i][1]+1;
        G[a].push_back({b, w[i]});
        G[b].push_back({a, w[i]});
    }

    int x=solve(1);
    if (x < INF) return x;
    return -1;
}

/*
#define MAX_N 500000

static int nv, kv;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&nv,&kv));
  for(i=0; i<nv-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = best_path(nv,kv,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

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