Submission #1016314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016314		Andrey	Closing Time (IOI23_closing)	C++17	83 / 100	1050 ms	38228 KiB

closing

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

long long n,x,y,k;
vector<pair<long long,long long>> haha[200001];
vector<long long> bruh(200001);
vector<long long> wow(200001);

void dfs(long long a, long long t, long long d, bool yeah) {
    if(yeah) {
        bruh[a] = d;
    }
    else {
        wow[a] = d;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+v.second,yeah);
        }
    }
}

bool dude(long long a, long long t) {
    if(a == y) {
        if(bruh[a] < wow[a]) {
            k-=bruh[a];
            wow[a]-=bruh[a];
            bruh[a] = 0;
        }
        else {
            k-=wow[a];
            bruh[a]-=wow[a];
            wow[a] = 0;
        }
        return true;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            if(dude(v.first,a)) {
                if(bruh[a] < wow[a]) {
                    k-=bruh[a];
                    wow[a]-=bruh[a];
                    bruh[a] = 0;
                }
                else {
                    k-=wow[a];
                    bruh[a]-=wow[a];
                    wow[a] = 0;
                }
                return true;
            }
        }
    }
    return false;
}

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++) {
        haha[i].clear();
    }
    for(long long i = 0; i < n-1; i++) {
        haha[U[i]].push_back({V[i],W[i]});
        haha[V[i]].push_back({U[i],W[i]});
    }
    long long ans = 0;
    dfs(x,-1,0,true);
    dfs(y,-1,0,false);
    vector<long long> wut(n);
    for(long long i = 0; i < n; i++) {
        wut[i] = min(bruh[i],wow[i]);
    }
    sort(wut.begin(),wut.end());
    long long sb = 0;
    for(long long i = 0; i < wut.size(); i++) {
        sb+=wut[i];
        if(sb > k) {
            break;
        }
        ans++;
    }
    dude(x,-1);
    if(k < 0) {
        return ans;
    }
    vector<long long> dp(2*n+1,LLONG_MAX/3);
    dp[0] = 0;
    for(long long i = 0; i < n; i++) {
        long long a = bruh[i],b = wow[i];
        if(a > b) {
            swap(a,b);
        }
        for(int j = 2*n; j >= 0; j--) {
            if(j > 0) {
                dp[j] = min(dp[j],dp[j-1]+a);
            }
            if(j > 1) {
                dp[j] = min(dp[j],dp[j-2]+b);
            }
        }
    }
    for(long long i = 0; i <= 2*n; i++) {
        if(dp[i] <= k) {
            ans = max(ans,i);
        }
    }
    return ans;
}

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 17