oj.uz

Submission #36289

# Submission time Handle Problem Language Result Execution time Memory
36289 2017-12-07T05:27:16 Z funcsr Race (IOI11_race) C++14
43 / 100
 833 ms 190720 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include "race.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
inline void chmin(int &x, int v) { if (x > v) x = v; }

int N, K;
int ans;
vector<P> G[200000];
void dfs(int x, int p, int r, int d) {
  if (d == K) ans = min(ans, r);
  for (P pp : G[x]) {
    int t = pp._1, nd = min(d+pp._2, INF);
    if (t == p) continue;
    dfs(t, x, r+1, nd);
  }
}

//int dp[200000][101][2];
//int src[200000][101];
const long long A = 200001, B = 40000400001LL; // A=N+1, B=(N+1)^2
long long data[200000][101];
inline long long encode(int dp0, int dp1, int src) { return dp1 + A*dp0 + B*src; }
inline void update(int x, int k, int v, int s) {
  long long d = data[x][k];
  int dp1 = d % A; d /= A;
  if (v >= dp1) return;
  int dp0 = d % A; d /= A;
  int src = d;

  if (v < dp0) {
    dp1 = dp0;
    dp0 = v;
    src = s;
  }
  else dp1 = v;
  data[x][k] = encode(dp0, dp1, src);
}
inline int get(int x, int k, int s) {
  long long d = data[x][k];
  int dp1 = d % A; d /= A;
  int dp0 = d % A; d /= A;
  int src = d;
  if (src == s) return dp1;
  return dp0;
}

void dfs2(int x, int p) {
  update(x, 0, 0, N);
  for (P pp : G[x]) {
    int t = pp._1, l = pp._2;
    if (t == p) continue;
    dfs2(t, x);
    for (int k=0; k<=K-l; k++) update(x, k+l, min(get(t, k, -1)+1, N), t);
  }
}

void dfs3(int x, int p, int pd) {
  if (p != -1) {
    for (int k=0; k<=K-pd; k++) update(x, k+pd, min(get(p, k, x)+1, N), p);
  }
  for (P pp : G[x]) {
    int t = pp._1, l = pp._2;
    if (t == p) continue;
    dfs3(t, x, l);
  }
  ans = min(ans, get(x, K, -1));
}

int best_path(int n, int k, int H[][2], int L[]) {
  N = n, K = k;
  rep(i, N) G[i].clear();
  rep(i, N-1) {
    G[H[i][0]].pb(P(H[i][1], L[i]));
    G[H[i][1]].pb(P(H[i][0], L[i]));
  }
  ans = INF;
  if (K <= 100) {
    // subtask 3
    rep(i, N) rep(j, K+1) data[i][j] = encode(N, N, N);
    dfs2(0, -1);
    dfs3(0, -1, -1);
    //rep(i, N) ans = min(ans, (int)dp[i][K][0]);
    if (ans >= N) ans = INF;
  }
  else if (N <= 1000) {
    // subtask 1&2
    rep(i, N) dfs(i, -1, 0, 0);
  }
  else abort();

  if (ans == INF) ans = -1;
  return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 6 ms 5296 KB Output is correct
5 Correct 7 ms 5364 KB Output is correct
6 Correct 5 ms 5364 KB Output is correct
7 Correct 8 ms 5364 KB Output is correct
8 Correct 7 ms 5364 KB Output is correct
9 Correct 6 ms 5364 KB Output is correct
10 Correct 6 ms 5364 KB Output is correct
11 Correct 7 ms 5364 KB Output is correct
12 Correct 6 ms 5364 KB Output is correct
13 Correct 6 ms 5364 KB Output is correct
14 Correct 6 ms 5364 KB Output is correct
15 Correct 9 ms 5364 KB Output is correct
16 Correct 7 ms 5364 KB Output is correct
17 Correct 6 ms 5408 KB Output is correct
18 Correct 6 ms 5408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 6 ms 5296 KB Output is correct
5 Correct 7 ms 5364 KB Output is correct
6 Correct 5 ms 5364 KB Output is correct
7 Correct 8 ms 5364 KB Output is correct
8 Correct 7 ms 5364 KB Output is correct
9 Correct 6 ms 5364 KB Output is correct
10 Correct 6 ms 5364 KB Output is correct
11 Correct 7 ms 5364 KB Output is correct
12 Correct 6 ms 5364 KB Output is correct
13 Correct 6 ms 5364 KB Output is correct
14 Correct 6 ms 5364 KB Output is correct
15 Correct 9 ms 5364 KB Output is correct
16 Correct 7 ms 5364 KB Output is correct
17 Correct 6 ms 5408 KB Output is correct
18 Correct 6 ms 5408 KB Output is correct
19 Correct 6 ms 5408 KB Output is correct
20 Correct 6 ms 5408 KB Output is correct
21 Correct 27 ms 5408 KB Output is correct
22 Correct 25 ms 5408 KB Output is correct
23 Correct 25 ms 5408 KB Output is correct
24 Correct 23 ms 5408 KB Output is correct
25 Correct 24 ms 5408 KB Output is correct
26 Correct 29 ms 5408 KB Output is correct
27 Correct 24 ms 5408 KB Output is correct
28 Correct 27 ms 5408 KB Output is correct
29 Correct 23 ms 5476 KB Output is correct
30 Correct 24 ms 5476 KB Output is correct
31 Correct 35 ms 5476 KB Output is correct
32 Correct 30 ms 5476 KB Output is correct
33 Correct 28 ms 5476 KB Output is correct
34 Correct 17 ms 5476 KB Output is correct
35 Correct 17 ms 5476 KB Output is correct
36 Correct 16 ms 5476 KB Output is correct
37 Correct 15 ms 5476 KB Output is correct
38 Correct 20 ms 5476 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 6 ms 5296 KB Output is correct
5 Correct 7 ms 5364 KB Output is correct
6 Correct 5 ms 5364 KB Output is correct
7 Correct 8 ms 5364 KB Output is correct
8 Correct 7 ms 5364 KB Output is correct
9 Correct 6 ms 5364 KB Output is correct
10 Correct 6 ms 5364 KB Output is correct
11 Correct 7 ms 5364 KB Output is correct
12 Correct 6 ms 5364 KB Output is correct
13 Correct 6 ms 5364 KB Output is correct
14 Correct 6 ms 5364 KB Output is correct
15 Correct 9 ms 5364 KB Output is correct
16 Correct 7 ms 5364 KB Output is correct
17 Correct 6 ms 5408 KB Output is correct
18 Correct 6 ms 5408 KB Output is correct
19 Correct 390 ms 89212 KB Output is correct
20 Correct 381 ms 89240 KB Output is correct
21 Correct 416 ms 89340 KB Output is correct
22 Correct 382 ms 89340 KB Output is correct
23 Correct 294 ms 89596 KB Output is correct
24 Correct 268 ms 89596 KB Output is correct
25 Correct 398 ms 93588 KB Output is correct
26 Correct 317 ms 98100 KB Output is correct
27 Correct 624 ms 172388 KB Output is correct
28 Correct 623 ms 190720 KB Output is correct
29 Correct 615 ms 190720 KB Output is correct
30 Correct 644 ms 190720 KB Output is correct
31 Correct 646 ms 190720 KB Output is correct
32 Correct 777 ms 190720 KB Output is correct
33 Correct 833 ms 190720 KB Output is correct
34 Correct 325 ms 190720 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 6 ms 5296 KB Output is correct
5 Correct 7 ms 5364 KB Output is correct
6 Correct 5 ms 5364 KB Output is correct
7 Correct 8 ms 5364 KB Output is correct
8 Correct 7 ms 5364 KB Output is correct
9 Correct 6 ms 5364 KB Output is correct
10 Correct 6 ms 5364 KB Output is correct
11 Correct 7 ms 5364 KB Output is correct
12 Correct 6 ms 5364 KB Output is correct
13 Correct 6 ms 5364 KB Output is correct
14 Correct 6 ms 5364 KB Output is correct
15 Correct 9 ms 5364 KB Output is correct
16 Correct 7 ms 5364 KB Output is correct
17 Correct 6 ms 5408 KB Output is correct
18 Correct 6 ms 5408 KB Output is correct
19 Correct 6 ms 5408 KB Output is correct
20 Correct 6 ms 5408 KB Output is correct
21 Correct 27 ms 5408 KB Output is correct
22 Correct 25 ms 5408 KB Output is correct
23 Correct 25 ms 5408 KB Output is correct
24 Correct 23 ms 5408 KB Output is correct
25 Correct 24 ms 5408 KB Output is correct
26 Correct 29 ms 5408 KB Output is correct
27 Correct 24 ms 5408 KB Output is correct
28 Correct 27 ms 5408 KB Output is correct
29 Correct 23 ms 5476 KB Output is correct
30 Correct 24 ms 5476 KB Output is correct
31 Correct 35 ms 5476 KB Output is correct
32 Correct 30 ms 5476 KB Output is correct
33 Correct 28 ms 5476 KB Output is correct
34 Correct 17 ms 5476 KB Output is correct
35 Correct 17 ms 5476 KB Output is correct
36 Correct 16 ms 5476 KB Output is correct
37 Correct 15 ms 5476 KB Output is correct
38 Correct 20 ms 5476 KB Output is correct
39 Correct 390 ms 89212 KB Output is correct
40 Correct 381 ms 89240 KB Output is correct
41 Correct 416 ms 89340 KB Output is correct
42 Correct 382 ms 89340 KB Output is correct
43 Correct 294 ms 89596 KB Output is correct
44 Correct 268 ms 89596 KB Output is correct
45 Correct 398 ms 93588 KB Output is correct
46 Correct 317 ms 98100 KB Output is correct
47 Correct 624 ms 172388 KB Output is correct
48 Correct 623 ms 190720 KB Output is correct
49 Correct 615 ms 190720 KB Output is correct
50 Correct 644 ms 190720 KB Output is correct
51 Correct 646 ms 190720 KB Output is correct
52 Correct 777 ms 190720 KB Output is correct
53 Correct 833 ms 190720 KB Output is correct
54 Correct 325 ms 190720 KB Output is correct
55 Runtime error 20 ms 190720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Halted 0 ms 0 KB -