Submission #958897

#	Time	Username	Problem	Language	Result	Execution time	Memory
958897		nguyentunglam	Closing Time (IOI23_closing)	C++17	8 / 100	116 ms	34244 KiB

closing

#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, x, y;
long long k;

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

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, ans = 0;

  for(auto &j : arr) {
    if (cur + j <= k) {
      cur += j;
      ans++;
    }
    else break;
  }
  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
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17