oj.uz

Submission #116286

# Submission time Handle Problem Language Result Execution time Memory
116286 2019-06-12T03:02:00 Z FieryPhoenix Race (IOI11_race) C++11
43 / 100
 3000 ms 24096 KB 
#include "race.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
#define INF 200001
#define MOD 1000000007

int N,K;
int H[200001][2];
int L[200001];
int subsize[200001];
vector<pair<int,int>>adj[200001];
bool dead[200001];
int dp[1000001]; //min edges to obtain length i
int temp[1000001];
int ans=INF;

int dfs(int node, int par){
  subsize[node]=1;
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par)
      subsize[node]+=dfs(v,node);
  }
  return subsize[node];
}

int dfs(int node, int par, int size){
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par && subsize[v]>size/2)
      return dfs(v,node,size);
  }
  return node;
}

vector<int>vec;
vector<int>vec2;

void dfs2(int node, int par, int numEdges, ll dis){
  if (dis>K)
    return;
  vec.push_back(dis);
  vec2.push_back(dis);
  temp[dis]=min(temp[dis],(int)numEdges);
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par)
      dfs2(v,node,numEdges+1,dis+adj[node][i].second);
  }
}

void solve(int node){
  int size=dfs(node,node);
  int centroid=dfs(node,node,size);
  dead[centroid]=true;
  for (int i=0;i<(int)vec2.size();i++)
    dp[vec2[i]]=INF;
  vec2.clear();
  for (int i=0;i<(int)adj[centroid].size();i++){
    int v=adj[centroid][i].first;
    if (!dead[v]){
      for (int i=1;i<=K;i++)
	temp[i]=INF;
      temp[0]=0;
      dfs2(v,centroid,1,adj[centroid][i].second);
      for (int j=0;j<(int)vec.size();j++)
	ans=min(ans,temp[vec[j]]+dp[K-vec[j]]);
      for (int j=0;j<(int)vec.size();j++){
	dp[vec[j]]=min(dp[vec[j]],temp[vec[j]]);
	temp[vec[j]]=INF;
      }
      vec.clear();
    }
  }
  for (int i=0;i<(int)adj[centroid].size();i++){
    int v=adj[centroid][i].first;
    if (!dead[v])
      solve(v);
  }
}

int best_path(int n, int k, int H[][2], int L[]){
  N=n;
  K=k;
  for (int i=0;i+1<N;i++){
    adj[H[i][0]].push_back({H[i][1],L[i]});
    adj[H[i][1]].push_back({H[i][0],L[i]});
  }
  for (int i=1;i<=K;i++)
    dp[i]=INF;
  solve(0);
  if (ans==INF)
    return -1;
  else
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 5 ms 4992 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 6 ms 5120 KB Output is correct
17 Correct 5 ms 5120 KB Output is correct
18 Correct 6 ms 5120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 5 ms 4992 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 6 ms 5120 KB Output is correct
17 Correct 5 ms 5120 KB Output is correct
18 Correct 6 ms 5120 KB Output is correct
19 Correct 5 ms 4992 KB Output is correct
20 Correct 6 ms 4992 KB Output is correct
21 Correct 6 ms 5120 KB Output is correct
22 Correct 405 ms 12348 KB Output is correct
23 Correct 340 ms 11128 KB Output is correct
24 Correct 384 ms 12024 KB Output is correct
25 Correct 376 ms 11768 KB Output is correct
26 Correct 157 ms 7808 KB Output is correct
27 Correct 375 ms 11512 KB Output is correct
28 Correct 95 ms 6776 KB Output is correct
29 Correct 152 ms 7800 KB Output is correct
30 Correct 173 ms 8056 KB Output is correct
31 Correct 303 ms 10360 KB Output is correct
32 Correct 350 ms 10872 KB Output is correct
33 Correct 365 ms 11264 KB Output is correct
34 Correct 280 ms 9848 KB Output is correct
35 Correct 341 ms 11648 KB Output is correct
36 Correct 367 ms 12416 KB Output is correct
37 Correct 304 ms 11384 KB Output is correct
38 Correct 217 ms 9088 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 5 ms 4992 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 6 ms 5120 KB Output is correct
17 Correct 5 ms 5120 KB Output is correct
18 Correct 6 ms 5120 KB Output is correct
19 Correct 172 ms 10548 KB Output is correct
20 Correct 155 ms 10488 KB Output is correct
21 Correct 163 ms 10744 KB Output is correct
22 Correct 142 ms 11312 KB Output is correct
23 Correct 101 ms 10616 KB Output is correct
24 Correct 82 ms 10616 KB Output is correct
25 Correct 180 ms 12408 KB Output is correct
26 Correct 104 ms 15604 KB Output is correct
27 Correct 208 ms 15992 KB Output is correct
28 Correct 388 ms 24096 KB Output is correct
29 Correct 387 ms 23364 KB Output is correct
30 Correct 202 ms 15992 KB Output is correct
31 Correct 206 ms 15992 KB Output is correct
32 Correct 254 ms 15864 KB Output is correct
33 Correct 393 ms 14812 KB Output is correct
34 Correct 317 ms 14808 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 5 ms 4992 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 6 ms 5120 KB Output is correct
17 Correct 5 ms 5120 KB Output is correct
18 Correct 6 ms 5120 KB Output is correct
19 Correct 5 ms 4992 KB Output is correct
20 Correct 6 ms 4992 KB Output is correct
21 Correct 6 ms 5120 KB Output is correct
22 Correct 405 ms 12348 KB Output is correct
23 Correct 340 ms 11128 KB Output is correct
24 Correct 384 ms 12024 KB Output is correct
25 Correct 376 ms 11768 KB Output is correct
26 Correct 157 ms 7808 KB Output is correct
27 Correct 375 ms 11512 KB Output is correct
28 Correct 95 ms 6776 KB Output is correct
29 Correct 152 ms 7800 KB Output is correct
30 Correct 173 ms 8056 KB Output is correct
31 Correct 303 ms 10360 KB Output is correct
32 Correct 350 ms 10872 KB Output is correct
33 Correct 365 ms 11264 KB Output is correct
34 Correct 280 ms 9848 KB Output is correct
35 Correct 341 ms 11648 KB Output is correct
36 Correct 367 ms 12416 KB Output is correct
37 Correct 304 ms 11384 KB Output is correct
38 Correct 217 ms 9088 KB Output is correct
39 Correct 172 ms 10548 KB Output is correct
40 Correct 155 ms 10488 KB Output is correct
41 Correct 163 ms 10744 KB Output is correct
42 Correct 142 ms 11312 KB Output is correct
43 Correct 101 ms 10616 KB Output is correct
44 Correct 82 ms 10616 KB Output is correct
45 Correct 180 ms 12408 KB Output is correct
46 Correct 104 ms 15604 KB Output is correct
47 Correct 208 ms 15992 KB Output is correct
48 Correct 388 ms 24096 KB Output is correct
49 Correct 387 ms 23364 KB Output is correct
50 Correct 202 ms 15992 KB Output is correct
51 Correct 206 ms 15992 KB Output is correct
52 Correct 254 ms 15864 KB Output is correct
53 Correct 393 ms 14812 KB Output is correct
54 Correct 317 ms 14808 KB Output is correct
55 Correct 35 ms 5752 KB Output is correct
56 Correct 15 ms 5756 KB Output is correct
57 Correct 81 ms 11380 KB Output is correct
58 Correct 44 ms 11500 KB Output is correct
59 Execution timed out 3041 ms 16884 KB Time limit exceeded
60 Halted 0 ms 0 KB -