oj.uz

Submission #843880

# Submission time Handle Problem Language Result Execution time Memory
843880 2023-09-04T16:26:19 Z nonono Closing Time (IOI23_closing) C++17
8 / 100
 139 ms 43456 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<pair<int, long long>>> ;

void dfs(int u, int par, const Graph& g, vector<long long>& dist) {
    for(auto [v, w] : g[u]) {
        if(v == par) continue ;
        
        dist[v] = dist[u] + w;
        dfs(v, u, g, dist);
    }
}

int sub1(int N, long long K, vector<long long> dX, vector<long long> dY) {
    vector<long long> a;
    
    for(int i = 0; i < N; i ++) {
        a.push_back(dX[i]);
        a.push_back(dY[i]);
    }
    
    sort(a.begin(), a.end());
    
    long long sum = 0;
    int ans = 0;
    
    for(long long x : a) {
        if(sum + x > K) break ;
        sum += x;
        ans += 1;
    }
    
    return ans;
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    
    Graph g(N);
    vector<long long> dX(N, 0), dY(N, 0);
    
    for(int i = 0; i < N - 1; i ++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    
    dfs(X, X, g, dX);
    dfs(Y, Y, g, dY);
    
    if(dX[Y] > 2 * K) return sub1(N, K, dX, dY);
}

// int main() {
//     int N, X, Y;
//     long long K;
//     cin >> N >> X >> Y >> K;
    
//     vector<int> U(N), V(N), W(N);
    
//     for(int i = 0; i < N - 1; i ++) {
//         cin >> U[i] >> V[i] >> W[i];
//     }
    
//     cout << max_score(N, X, Y, K, U, V, W) << "\n";
//     return 0;
// }

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:40:14: warning: control reaches end of non-void function [-Wreturn-type]
   40 |     Graph g(N);
      |              ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 37060 KB Output is correct
2 Correct 139 ms 43456 KB Output is correct
3 Correct 72 ms 3016 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -