oj.uz

Submission #840056

# Submission time Handle Problem Language Result Execution time Memory
840056 2023-08-31T03:26:50 Z socpite Closing Time (IOI23_closing) C++17
8 / 100
 134 ms 36572 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const long long INF = 1e18;

int vis[maxn], onp[maxn];
long long depX[maxn], depY[maxn];

vector<pair<int, int>> g[maxn];

void dfsX(int x, int p){
    for(auto v: g[x]){
        if(v.first == p)continue;
        depX[v.first] = depX[x] + v.second;
        dfsX(v.first, x);
    }
}

void dfsY(int x, int p){
    for(auto v: g[x]){
        if(v.first == p)continue;
        depY[v.first] = depY[x] + v.second;
        dfsY(v.first, x);
    }
}

long long solve1(int n, long long k) {
    vector<long long> vec;
    vec.insert(vec.end(), depX, depX + n);
    vec.insert(vec.end(), depY, depY + n);
    sort(vec.begin(), vec.end());
    long long crr = 0;
    for(int i = 0; i < vec.size(); i++){
        crr += vec[i];
        if(crr > k)return i;
    }
    return vec.size();
}

vector<int> path;

bool dfs_path(int x, int p, int endp){
    if(x == endp)return (onp[x] = true);
    for(auto v: g[x]){
        if(v.first == p)continue;
        onp[x] |= dfs_path(v.first, x, endp);
    }
    return onp[x];
}

long long solve2(int n, long long k, int x, int y) {
    dfs_path(x, 0, y);
    long long re = 0;
    vector<long long> vec;
    for(int i = 0; i < n; i++){
        if(onp[i]){
            k -= min(depX[i], depY[i]);
            re++;
            vec.push_back(max(depX[i], depY[i]) - min(depX[i], depY[i]));
        }
        else {
            vec.push_back(min(depX[i], depY[i]));
            vec.push_back(max(depX[i], depY[i]) - min(depX[i], depY[i]));
        }
    }
    if(k < 0)return 0;
    sort(vec.begin(), vec.end());
    long long crr = 0;
    for(int i = 0; i < vec.size(); i++){
        crr += vec[i];
        if(crr > k)return i + re;
    }
    return vec.size() + re;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for (int i = 0; i < N; i++)
        g[i].clear();
    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]});
    }
    depX[X] = 0;
    depY[Y] = 0;
    dfsX(X, 0);
    dfsY(Y, 0);
    long long ans = max(solve1(N, K), solve2(N, K, X, Y));
    

    return ans;
}

Compilation message

closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 31108 KB Output is correct
2 Correct 134 ms 36572 KB Output is correct
3 Correct 68 ms 7716 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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