oj.uz

Submission #115116

# Submission time Handle Problem Language Result Execution time Memory
115116 2019-06-05T10:48:23 Z oolimry Race (IOI11_race) C++14
0 / 100
 16 ms 16000 KB 
#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;

static vector<ii> adj[200005];
static bool vis[200005];
unordered_map<int,int> dp[200005];
int k;
int ans = 102345678;
void dfs(int u){
  vis[u] = true;
  for(int i = 0;i < adj[u].size();i++){
    int v = adj[u][i].first;
    int w = adj[u][i].second;

    if(vis[v]) continue;
    dfs(v);
    vector<ii> updates;
    if(dp[v].size() > dp[u].size()) swap(dp[u],dp[v]);
    for(ii x : dp[v]){
      int value = w + x.first;
      if(value <= k){
        if(dp[u].find(k-value) != dp[u].end()){
          ans = min(ans, dp[u][k-value] + x.second + 1);
        }
        updates.push_back({value,x.second+1});
      }
    }
    dp[v].clear();

    for(ii x : updates){
      if(dp[u].find(x.first) == dp[u].end()){
        dp[u][x.first] = x.second;
      }
      else{
        dp[u][x.first] = min(x.second,dp[u][x.first]);
      }
    }
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  int n = N;
  for(int i = 0;i < n;i++) dp[i][0] = 0;
  for(int i = 0;i < n-1;i++){
    int a = H[i][0];
    int b = H[i][1];
    int c = L[i];
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
  }

  dfs(0);
  if(ans > n) return -1;
  return ans;
}

Compilation message

race.cpp: In function 'void dfs(int)':
race.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i < adj[u].size();i++){
                 ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -