oj.uz

Submission #962543

# Submission time Handle Problem Language Result Execution time Memory
962543 2024-04-13T19:01:46 Z tutis Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 28824 KB 
#include "closing.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W) {
    vector <pair<int, int>> adj[N];
    for (int i = 0; i < N - 1; i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    vector <ll> D[2];
    D[0] = vector<ll>(N);
    D[1] = vector<ll>(N);
    int XY[2] = {X, Y};
    vector<int> x2y;
    for (int t: {0, 1}) {
        D[t][XY[t]] = 0;
        vector<int> P;
        function<void(int, int)> dfs = [&](int i, int p) -> void {
            P.push_back(i);
            if (t == 0 && i == Y) {
                x2y = P;
            }
            for (auto j: adj[i]) {
                if (j.first == p) {
                    continue;
                }
                D[t][j.first] = D[t][i] + j.second;
                dfs(j.first, i);
            }
            P.pop_back();
        };
        dfs(XY[t], -1);
    }
    int ret = 0;
    ll S[2][x2y.size()];
    ll s = 0;
    for (int i = 0; i < x2y.size(); i++) {
        s += D[0][x2y[i]];
        s = min(s, K + 1);
        S[0][i] = s;
    }
    s = 0;
    for (int j = x2y.size() - 1; j >= 0; j--) {
        s += D[1][x2y[j]];
        s = min(s, K + 1);
        S[1][j] = s;
    }
    for (int i = 0; i < x2y.size(); i++) {
        for (int j = x2y.size() - 1; j > i; j--) {
            if (S[0][i] + S[1][j] <= K) {
                ret = max(ret, i + 1 + (int(x2y.size()) - j));
            }
        }
    }
    int m = 0;
    while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
        m++;
    }
    if (S[0][m] + S[1][m + 1] <= K) {
        ll X[2][x2y.size()];
        ll s = 0;
        X[0][m + 1] = 0;
        for (int i = m; i >= 0; i--) {
            s += D[1][x2y[i]] - D[0][x2y[i]];
            s = min(s, K + 1);
            X[0][i] = s;
        }
        s = 0;
        X[1][m] = 0;
        for (int j = m + 1; j < x2y.size(); j++) {
            s += D[0][x2y[j]] - D[1][x2y[j]];
            s = min(s, K + 1);
            X[1][j] = s;
        }
        for (int i = 0; i <= m + 1; i++) {
            for (int j = x2y.size() - 1; j >= m; j--) {
                if (S[0][m] + S[1][m + 1] + X[0][i] + X[1][j] <= K) {
                    ret = max(ret, int(x2y.size()) + (m + 1 - i) + (j - m));
                }
            }
        }
    }
    return ret;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < x2y.size(); i++) {
      |                     ~~^~~~~~~~~~~~
closing.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < x2y.size(); i++) {
      |                     ~~^~~~~~~~~~~~
closing.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
      |            ~~~~~~^~~~~~~~~~~~
closing.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = m + 1; j < x2y.size(); j++) {
      |                             ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 28824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -