제출 #339070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339070		bigDuck	경주 (Race) (IOI11_race)	C++14	31 / 100	306 ms	111596 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int n, k;
vector<pii> g[200010];
bool v[200010];
int mn[200010][101];
int res=1e9;


void dfs(int s){
v[s]=true;
mn[s][0]=1;
for(auto pr:g[s]){
    int u=pr.ft, d=pr.sc;
    if(!v[u]){
        dfs(u);

        for(int sum=0; (sum+d)<=( k ); sum++){
            if( (mn[s][k-(sum+d) ]>0) && (mn[u][sum]>0) ){
                res=min(res, mn[s][k-(sum+d)]+mn[u][sum]);
            }
        }

        for(int sum=0; ( (sum+d)<=k ); sum++){
            if( (mn[u][sum]>0) ){
                if(mn[s][sum+d]==0){
                    mn[s][sum+d]=mn[u][sum]+1;
                }
                else{
                    mn[s][sum+d]=min(mn[s][sum+d], mn[u][sum]+1);
                }
            }
        }
    }
}

if(mn[s][k]>0){
    res=min(res, mn[s][k]);
}


return;
}



int best_path(int N, int K, int H[][2], int L[])
{
  n=N; k=K;

  for(int i=0; i<n; i++){
    int u=H[i][0]+1, v=H[i][1]+1, d=L[i];
    g[u].pb({v, d}); g[v].pb({u, d});
  }

    dfs(1);

  if(res==(1e9)){
    return -1;
  }
  return res-1;
}

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