oj.uz

답안 #958897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958897 2024-04-07T03:21:25 Z nguyentunglam 봉쇄 시간 (IOI23_closing) C++17
8 / 100
 116 ms 34244 KB 
#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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 29376 KB Output is correct
2 Correct 116 ms 34244 KB Output is correct
3 Correct 64 ms 13908 KB Output is correct

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8796 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -