oj.uz

Submission #1004405

# Submission time Handle Problem Language Result Execution time Memory
1004405 2024-06-21T08:39:46 Z Gray Race (IOI11_race) C++17
0 / 100
 1 ms 1116 KB 
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<bool> black;
vector<ll> sz;
ll n, k;
ll getsz(ll u, ll p){
  sz[u]=1;
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    sz[u]+=getsz(v, u);
  }
  return sz[u];
}
void findcentroid(ll u, ll p, ll up, ll &centr, ll wsz){
  bool pos=(up<=wsz/2);
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    if (sz[v]>wsz/2) pos=0;
    findcentroid(v, u, up+1, centr, wsz);
  }
  if (pos) centr=u;
}
void dfs(ll u, ll p, map<ll, ll> &usg, ll level, ll dep){
  if (usg.count(level)) usg[level]=min(usg[level], dep);
  else usg[level]=dep;
  for (auto i:A[u]){
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p or black[i]) continue;
    dfs(v, u, usg, level+e[i].ff, dep+1);
  }
}
void cedfs(ll u, ll &mn, ll wsz){
  ll centr = -1;
  findcentroid(u,u, 0, centr, wsz);
  assert(centr!=-1);
  map<ll, ll> full, levs;
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    dfs(v, v, levs, e[i].ff, 1);    
    for (auto [length, tim]:levs){
      // cout << length << "-" << tim << ' ';
      if (full.count(k-length)){
        mn=min(mn, full[k-length]+tim);
      }
      if (length==k){
        mn=min(mn, tim);
      }
    }
    // cout << ln;
    for (auto [length, tim]:levs){
      if (full.count(length)){
        full[length]=min(full[length], tim);
      }else{
        full[length]=tim;
      }
    }
  }
  for (auto i:A[u]){
    if (black[i]) continue;
    black[i]=1;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    cedfs(v, mn, getsz(v, v));
  }
}


int best_path(int N, int K, int H[][2], int L[])
{
  n = N; k=K;
  e.resize(N-1);
  A.resize(N);
  for (ll i=0; i<n-1; i++){
    A[H[i][0]].push_back(i);
    A[H[i][1]].push_back(i);
    e[i] = {L[i], {H[i][0], H[i][1]}};
  }
  black.resize(N);
  sz.resize(N);
  ll mn = 2e18;
  cedfs(0, mn, getsz(0, 0));
  return (mn==2e18?-1:mn);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -