Submission #841676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
841676	2023-09-01T20:35:03 Z	garyye	Closing Time (IOI23_closing)	C++17	8 / 100	113 ms	36676 KB

closing

#include "closing.h"

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


typedef long long ll;
typedef pair<int, int> i2;
typedef tuple<ll, int, int, int> i4;

struct Cmp {
  bool operator()(const i4& a, const i4& b) const {
    return get<0>(a) > get<0>(b);
  }
};

typedef priority_queue<i4, vector<i4>, Cmp> heap4;

int max_score(int N, int X, int Y, ll K, 
    vector<int> U, vector<int> V, vector<int> W) {
  vector<vector<i2>> E(N);

  for(int i = 0; i < N - 1; ++i) {
    E[U[i]].push_back({V[i], W[i]});
    E[V[i]].push_back({U[i], W[i]});
  }

  auto calc_dist = [&](int s) {
    vector<ll> D(N, 0);
    function<void(int, int)> rec;
    rec = [&](int u, int p) {
      for(const auto& [v, w] : E[u]) {
        if(v != p) {
          D[v] = D[u] + w;
          rec(v, u);
        }
      }
    };
    rec(s, -1);
    return D;
  };

  auto find_path = [&]() {
    vector<int> path;
    function<bool(int, int)> rec;
    rec = [&](int u, int p) {
      path.push_back(u);
      if(u == Y) {
        return true;
      }
      for(const auto& [v, _] : E[u]) {
        if(v != p && rec(v, u)) {
          return true;
        }
      }
      path.pop_back();
      return false;
    };
    rec(X, -1);
    return path;
  };


  vector<vector<ll>> D = {calc_dist(X), calc_dist(Y)};

  auto solve = [&](heap4& pq, ll k, bool cross) {
    int s = 0;
    while(!pq.empty()) {
      auto [d, u, p, c] = pq.top(); pq.pop();
      if(d > k) {
        break;
      }
      s++;
      k -= d;
      for(auto [v, w]: E[u]) {
        if(v != p) {
          int b = -1;
          // w > 0, so can't be equal
          if(D[c][v] < D[1-c][v]) {
            b = D[c][v];
          } else if(cross) {
            b = D[c][v] - D[1-c][v];
          }
          if(b != -1) {
            pq.emplace(b, v, u, c);
          }

        }
      }
    }
    return s;
  };


  int ans;
  {
    heap4 pq;
    pq.emplace(0, X, -1, 0);
    pq.emplace(0, Y, -1, 1);
    ans = solve(pq, K, false);
  }


  {
    ll k = K;
    vector<int> P = find_path();

    for(int j = 0; j < P.size(); ++j) {
      k -= min(D[0][P[j]], D[1][P[j]]);
    }

    int i;
    for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
    i--;

    heap4 pq;
    for(auto [v, w]: E[X]) if(v != P[1])          pq.emplace(w, v, X, 0);
    for(auto [v, w]: E[Y]) if(v != P[P.size()-2]) pq.emplace(w, v, Y, 1);

    pq.emplace(D[0][P[i+1]] - D[1][P[i+1]], P[i+1], P[i], 0);
    pq.emplace(D[1][P[i]] - D[0][P[i]], P[i], P[i+1], 1);

    if(k >= 0) {
      ans = max(ans, (int) P.size() + solve(pq, k, true));
    }
  }

  return ans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int j = 0; j < P.size(); ++j) {
      |                    ~~^~~~~~~~~~
closing.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
      |                ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	29776 KB	Output is correct
2	Correct	113 ms	36676 KB	Output is correct
3	Correct	62 ms	2804 KB	Output is correct

Subtask #2
0.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
3	Halted	0 KB	-

Subtask #3
0.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
3	Halted	0 KB	-

Subtask #4
0.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
3	Halted	0 KB	-

Subtask #5
0.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
4	Halted	0 KB	-

Subtask #6
0.0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
4	Halted	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
4	Halted	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
4	Halted	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '35'
4	Halted	0 KB	-