oj.uz

Submission #958909

# Submission time Handle Problem Language Result Execution time Memory
958909 2024-04-07T03:51:38 Z nguyentunglam Closing Time (IOI23_closing) C++17
51 / 100
 647 ms 200124 KB 
#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, M = 3010;

int n, x, y;
long long k;

long long d[N], dx[N], dy[N];

long long f[M][M];

vector<pair<int, int> > adj[N];

void dfs(int u, int p) {
//  cerr << u << " " << p << endl;
  for(auto &[v, w] : adj[u]) if (v != p) {
    d[v] = d[u] + w;
    dfs(v, u);
  }
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
  n = N; x = X; y = Y; k = K;
  for(int i = 0; i < n; i++) adj[i].clear();
  for(int i = 0; i < n - 1; i++) {
    adj[U[i]].emplace_back(V[i], W[i]);
    adj[V[i]].emplace_back(U[i], W[i]);
  }
  d[x] = 0;
  dfs(x, x);
  for(int i = 0; i < n; i++) dx[i] = d[i];
  d[y] = 0;
  dfs(y, y);
  for(int i = 0; i < n; i++) dy[i] = d[i];

  vector<long long> arr;
  for(int i = 0; i < n; i++) {
    arr.push_back(dx[i]);
    arr.push_back(dy[i]);
  }

  sort(arr.begin(), arr.end());
//  for(auto &j : arr) cout << j << " "; cout << endl;

  long long cur = 0;
  int ans = 0;

  for(auto &j : arr) {
    if (cur + j <= k) {
      cur += j;
      ans++;
    }
    else break;
  }

  for(int i = 1; i <= n; i++) for(int j = 0; j <= 2 * n; j++) f[i][j] = 1e16;

  for(int i = 0; i < n; i++) for(int j = 0; j <= 2 * i; j++) {
    if (dx[i] + dy[i] == dx[y]) {
      f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + min(dx[i], dy[i]));
      f[i + 1][j + 2] = min(f[i + 1][j + 2], f[i][j] + max(dx[i], dy[i]));
    }
    else {
      f[i + 1][j] = min(f[i + 1][j], f[i][j]);
      f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + min(dx[i], dy[i]));
      f[i + 1][j + 2] = min(f[i + 1][j + 2], f[i][j] + max(dx[i], dy[i]));
    }
  }

  for(int j = 1; j <= 2 * n; j++) if (f[n][j] <= k) ans = max(ans, j);

  return ans;
}

#ifdef ngu
int main()
{
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
#endif // ngu

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 647 ms 200124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12920 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12928 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12920 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12928 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 2 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 15192 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 4 ms 23152 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 5 ms 23128 KB Output is correct
23 Correct 4 ms 23132 KB Output is correct
24 Correct 4 ms 23128 KB Output is correct

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12920 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12928 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 2 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 15192 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 4 ms 23152 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 5 ms 23128 KB Output is correct
23 Correct 4 ms 23132 KB Output is correct
24 Correct 4 ms 23128 KB Output is correct
25 Correct 4 ms 12892 KB Output is correct
26 Incorrect 36 ms 81000 KB 1st lines differ - on the 1st token, expected: '5595', found: '6000'
27 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12920 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12916 KB Output is correct
9 Correct 2 ms 12912 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12924 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 2 ms 12912 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 2 ms 12892 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 2 ms 12892 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12920 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12928 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 15192 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 3 ms 12916 KB Output is correct
21 Correct 2 ms 12912 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 2 ms 12924 KB Output is correct
24 Correct 2 ms 12888 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 2 ms 12892 KB Output is correct
27 Correct 2 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 2 ms 12892 KB Output is correct
30 Correct 2 ms 12912 KB Output is correct
31 Correct 2 ms 12892 KB Output is correct
32 Correct 4 ms 12892 KB Output is correct
33 Correct 2 ms 12892 KB Output is correct
34 Correct 2 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 3 ms 12892 KB Output is correct
39 Correct 2 ms 14940 KB Output is correct
40 Correct 3 ms 14940 KB Output is correct
41 Correct 2 ms 14940 KB Output is correct
42 Correct 3 ms 14940 KB Output is correct
43 Correct 2 ms 14940 KB Output is correct
44 Correct 2 ms 14936 KB Output is correct
45 Correct 3 ms 14940 KB Output is correct
46 Correct 3 ms 14940 KB Output is correct
47 Correct 3 ms 14940 KB Output is correct
48 Correct 3 ms 14940 KB Output is correct
49 Correct 3 ms 12892 KB Output is correct
50 Correct 2 ms 12892 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12920 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12928 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 15192 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 4 ms 23152 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 5 ms 23128 KB Output is correct
24 Correct 4 ms 23132 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 2 ms 12892 KB Output is correct
27 Correct 3 ms 12916 KB Output is correct
28 Correct 2 ms 12912 KB Output is correct
29 Correct 2 ms 12892 KB Output is correct
30 Correct 2 ms 12924 KB Output is correct
31 Correct 2 ms 12888 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 2 ms 12892 KB Output is correct
34 Correct 2 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 2 ms 12892 KB Output is correct
37 Correct 2 ms 12912 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 4 ms 12892 KB Output is correct
40 Correct 2 ms 12892 KB Output is correct
41 Correct 2 ms 12892 KB Output is correct
42 Correct 2 ms 12892 KB Output is correct
43 Correct 3 ms 12892 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Correct 3 ms 12892 KB Output is correct
46 Correct 2 ms 14940 KB Output is correct
47 Correct 3 ms 14940 KB Output is correct
48 Correct 2 ms 14940 KB Output is correct
49 Correct 3 ms 14940 KB Output is correct
50 Correct 2 ms 14940 KB Output is correct
51 Correct 2 ms 14936 KB Output is correct
52 Correct 3 ms 14940 KB Output is correct
53 Correct 3 ms 14940 KB Output is correct
54 Correct 3 ms 14940 KB Output is correct
55 Correct 3 ms 14940 KB Output is correct
56 Correct 3 ms 12892 KB Output is correct
57 Correct 2 ms 12892 KB Output is correct
58 Correct 3 ms 12892 KB Output is correct
59 Correct 3 ms 14940 KB Output is correct
60 Correct 3 ms 14940 KB Output is correct
61 Correct 4 ms 14940 KB Output is correct
62 Correct 3 ms 14940 KB Output is correct
63 Correct 5 ms 23132 KB Output is correct
64 Correct 4 ms 23132 KB Output is correct
65 Correct 4 ms 23104 KB Output is correct
66 Correct 4 ms 23132 KB Output is correct
67 Correct 4 ms 23132 KB Output is correct
68 Correct 4 ms 23132 KB Output is correct
69 Correct 4 ms 23132 KB Output is correct
70 Correct 5 ms 23132 KB Output is correct
71 Correct 4 ms 23132 KB Output is correct
72 Correct 4 ms 23132 KB Output is correct
73 Correct 4 ms 21172 KB Output is correct
74 Correct 4 ms 21080 KB Output is correct
75 Correct 3 ms 14936 KB Output is correct

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12920 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12928 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 15192 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 4 ms 23152 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 5 ms 23128 KB Output is correct
24 Correct 4 ms 23132 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Incorrect 36 ms 81000 KB 1st lines differ - on the 1st token, expected: '5595', found: '6000'
28 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12920 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12928 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 15192 KB Output is correct
17 Correct 3 ms 15192 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 4 ms 23152 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 5 ms 23128 KB Output is correct
24 Correct 4 ms 23132 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Incorrect 36 ms 81000 KB 1st lines differ - on the 1st token, expected: '5595', found: '6000'
28 Halted 0 ms 0 KB -