oj.uz

Submission #116285

# Submission time Handle Problem Language Result Execution time Memory
116285 2019-06-12T03:00:00 Z FieryPhoenix Race (IOI11_race) C++11
43 / 100
 3000 ms 24056 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 2001001001
#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];
ll dp[1000001]; //min edges to obtain length i
ll temp[1000001];
ll 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],(ll)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 5 ms 5120 KB Output is correct
2 Correct 6 ms 4992 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 5072 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 5052 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 5 ms 4992 KB Output is correct
12 Correct 5 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 8 ms 5120 KB Output is correct
17 Correct 6 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 4992 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 5072 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 5052 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 5 ms 4992 KB Output is correct
12 Correct 5 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 8 ms 5120 KB Output is correct
17 Correct 6 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 7 ms 4992 KB Output is correct
20 Correct 5 ms 4992 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 533 ms 19564 KB Output is correct
23 Correct 396 ms 16888 KB Output is correct
24 Correct 440 ms 18688 KB Output is correct
25 Correct 444 ms 18304 KB Output is correct
26 Correct 178 ms 10488 KB Output is correct
27 Correct 423 ms 17700 KB Output is correct
28 Correct 103 ms 8192 KB Output is correct
29 Correct 165 ms 10360 KB Output is correct
30 Correct 186 ms 11000 KB Output is correct
31 Correct 349 ms 15360 KB Output is correct
32 Correct 359 ms 16308 KB Output is correct
33 Correct 396 ms 17528 KB Output is correct
34 Correct 277 ms 14336 KB Output is correct
35 Correct 381 ms 17912 KB Output is correct
36 Correct 418 ms 19712 KB Output is correct
37 Correct 359 ms 17636 KB Output is correct
38 Correct 243 ms 13160 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 4992 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 5072 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 5052 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 5 ms 4992 KB Output is correct
12 Correct 5 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 8 ms 5120 KB Output is correct
17 Correct 6 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 181 ms 10492 KB Output is correct
20 Correct 157 ms 10616 KB Output is correct
21 Correct 177 ms 10764 KB Output is correct
22 Correct 178 ms 11284 KB Output is correct
23 Correct 121 ms 10588 KB Output is correct
24 Correct 90 ms 10488 KB Output is correct
25 Correct 183 ms 12536 KB Output is correct
26 Correct 104 ms 15432 KB Output is correct
27 Correct 231 ms 15992 KB Output is correct
28 Correct 389 ms 24056 KB Output is correct
29 Correct 395 ms 23416 KB Output is correct
30 Correct 210 ms 16120 KB Output is correct
31 Correct 216 ms 16120 KB Output is correct
32 Correct 257 ms 16092 KB Output is correct
33 Correct 298 ms 14748 KB Output is correct
34 Correct 322 ms 14916 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 4992 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 5072 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 5052 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 5 ms 4992 KB Output is correct
12 Correct 5 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 8 ms 5120 KB Output is correct
17 Correct 6 ms 5120 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 7 ms 4992 KB Output is correct
20 Correct 5 ms 4992 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 533 ms 19564 KB Output is correct
23 Correct 396 ms 16888 KB Output is correct
24 Correct 440 ms 18688 KB Output is correct
25 Correct 444 ms 18304 KB Output is correct
26 Correct 178 ms 10488 KB Output is correct
27 Correct 423 ms 17700 KB Output is correct
28 Correct 103 ms 8192 KB Output is correct
29 Correct 165 ms 10360 KB Output is correct
30 Correct 186 ms 11000 KB Output is correct
31 Correct 349 ms 15360 KB Output is correct
32 Correct 359 ms 16308 KB Output is correct
33 Correct 396 ms 17528 KB Output is correct
34 Correct 277 ms 14336 KB Output is correct
35 Correct 381 ms 17912 KB Output is correct
36 Correct 418 ms 19712 KB Output is correct
37 Correct 359 ms 17636 KB Output is correct
38 Correct 243 ms 13160 KB Output is correct
39 Correct 181 ms 10492 KB Output is correct
40 Correct 157 ms 10616 KB Output is correct
41 Correct 177 ms 10764 KB Output is correct
42 Correct 178 ms 11284 KB Output is correct
43 Correct 121 ms 10588 KB Output is correct
44 Correct 90 ms 10488 KB Output is correct
45 Correct 183 ms 12536 KB Output is correct
46 Correct 104 ms 15432 KB Output is correct
47 Correct 231 ms 15992 KB Output is correct
48 Correct 389 ms 24056 KB Output is correct
49 Correct 395 ms 23416 KB Output is correct
50 Correct 210 ms 16120 KB Output is correct
51 Correct 216 ms 16120 KB Output is correct
52 Correct 257 ms 16092 KB Output is correct
53 Correct 298 ms 14748 KB Output is correct
54 Correct 322 ms 14916 KB Output is correct
55 Correct 35 ms 5880 KB Output is correct
56 Correct 15 ms 5760 KB Output is correct
57 Correct 82 ms 11476 KB Output is correct
58 Correct 48 ms 11628 KB Output is correct
59 Execution timed out 3006 ms 18424 KB Time limit exceeded
60 Halted 0 ms 0 KB -