Submission #938626

#	Time	Username	Problem	Language	Result	Execution time	Memory
938626		duckindog	Race (IOI11_race)	C++17	21 / 100	127 ms	262144 KiB

race

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "race.h"
#endif

const int N = 200'000 + 10;
vector<pair<int, int>> ad[N];

namespace sub1 {
  long long d[N];
  int solve(int n, int k, int l[]) { 
    for (int i = 1; i < n; ++i) d[i] = d[i - 1] + l[i - 1];
    int answer = 1e7;
    for (int i = 1; i < n; ++i) 
      for (int j = i; j < n; ++j) 
        if (d[j] - d[i - 1] == k) answer = min(answer, j - i + 1);
      
    return answer == 1e7 ? -1 : answer; 
  }

}

namespace sub2 {
  long long d[N], dep[N];
  int f[N][10], st[N], ed[N], it;
  void dfs(int u, int pre = 0) { 
    st[u] = ++it;
    for (int i = 1; i <= 9; ++i)
      f[u][i] = f[f[u][i - 1]][i - 1];

    for (const auto& [v, w] : ad[u]) { 
      if (v == pre) continue;
      d[v] = d[u] + w;
      dep[v] = dep[u] + 1;
      f[v][0] = u;
      dfs(v, u);
    }
    ed[u] = it;
  }
  bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
  int lca(int u, int v) { 
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;

    for (int i = 9; i >= 0; --i)
      if (!anc(f[u][i], v)) u = f[u][i];
    return f[u][0];
  }

  int solve(int n, int k) { 
    dfs(0);
    long long answer = 1e7;
    for (int i = 0; i < n; ++i) { 
      for (int j = i + 1; j < n; ++j) { 
        int l = lca(i, j);
        int distant = d[i] + d[j] - 2 * d[l];
        if (distant == k) answer = min(answer, dep[i] + dep[j] - 2 * dep[l]);
      }
    }

    return answer == 1e7 ? -1 : answer; 
  }

}

namespace sub3 {
  long long dpin[N][110], dpout[N][110];
  int n, k;
  void dfs1(int u, int pre = 0) { 
    dpin[u][0] = 0;
    for (const auto& [v, w] : ad[u]) { 
      if (v == pre) continue;
      dfs1(v, u);
      for (int i = 0; i <= k; ++i) { 
        if (i - w >= 0) dpin[u][i] = min(dpin[u][i], dpin[v][i - w] + 1);
      }
    }
  }

  void dfs2(int u, int pre = 0) { 
    dpout[u][0] = 0;
    vector<vector<pair<int, int>>> best(k + 1);
    for (const auto&[v, w] : ad[u]) { 
      if (v == pre) continue;
      for (int i = 0; i <= k; ++i) if (i - w >= 0) best[i].push_back({dpin[v][i - w], v});
    }
    
    for (int i = 0; i <= k; ++i) {
      best[i].push_back({1e7, -1}); best[i].push_back({1e7, -1});
      sort(best[i].begin(), best[i].end());
    }
    
    for (const auto&[v, w] : ad[u]) { 
      if (v == pre) continue;
      for (int i = 0; i <= k; ++i) { 
        if (i - w < 0) continue;
        int nv = (best[i - w][0].second == v ? 1 : 0);
        dpout[v][i] = best[i - w][nv].first + 2;
        dpout[v][i] = min(dpout[v][i], dpout[u][i - w] + 1);
      }
      dfs2(v, u);
    }
  }

  int solve(int a, int b) { 
    n = a; k = b;
    memset(dpin, 63, sizeof dpin);
    memset(dpout, 63, sizeof dpout);
    dfs1(0); dfs2(0);
    long long answer = 1e7;
    for (int i = 0; i <= n; ++i) { 
      answer = min({answer, dpin[i][k], dpout[i][k]});
    }
    return (answer > n ? -1 : answer);
  }

}

int best_path(int n, int k, int h[][2], int l[]) { 
  int sub = 1;
  for (int i = 0; i < n - 1; ++i) { 
    int u = h[i][0], v = h[i][1], w = l[i];
    if (u > v) swap(u, v);
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
    if (u != i || v != i + 1 && sub == 1) sub = 2;
  }
  if (sub > 1) sub = (n <= 1000 ? 2 : k <= 100 ? 3 : 4);
  
  if (sub == 1) return sub1::solve(n, k, l);
  if (sub == 2) return sub2::solve(n, k);
  if (sub == 3) return sub3::solve(n, k);
  return -1;
} 

#ifdef LOCAL
#define MAX_AA 500000
static int AA, K;
static int H[MAX_AA][2];
static int L[MAX_AA];
static int solution;

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

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&AA,&K));
  for(i=0; i<AA-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(AA,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
#endif

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:129:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  129 |     if (u != i || v != i + 1 && sub == 1) sub = 2;
      |                   ~~~~~~~~~~~^~~~~~~~~~~

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