Submission #840454

#	Time	Username	Problem	Language	Result	Execution time	Memory
840454		socpite	Closing Time (IOI23_closing)	C++17	75 / 100	90 ms	10956 KiB

closing

#include "closing.h"
 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e3+5;
const long long INF = 1e18;
 
int onp[maxn];
long long depX[maxn], depY[maxn];
 
vector<pair<int, int>> g[maxn];
 
 
 
void dfsX(int x, int p = -1)
{
    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 = -1)
{
    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 endp, int p = -1)
{
    if (x == endp)
        return (onp[x] = true);
    for (auto v : g[x])
    {
        if (v.first == p)
            continue;
        onp[x] |= dfs_path(v.first, endp, x);
    }
    return onp[x];
}
 
vector<long long> vec1, vec2;
 
void dfs_gen(int x, int p, long long cnst){
    long long val;
    if(p == -1)val = 0;
    else val = min(depX[x],depY[x]);
    if(val > cnst)vec2.push_back(val);
    else vec1.push_back(val);
    for(auto v: g[x]){
        if(v.first == p || onp[v.first])continue;
        dfs_gen(v.first, x, cnst);
    }
}

vector<long long> v1;
vector<pair<long long, long long>> v2;
vector<long long> mn;
int ptr;
long long mx, sum;

long long solve_v2(long long k){
    if(k < 0)return -INF;
    while(ptr < v2.size() && v2[ptr].first + sum <= k) {
        mx = max(mx, v2[ptr].first - v2[ptr].second);
        sum += v2[ptr].first;
        ptr++;
    }
    if(ptr == v2.size())return 2*ptr;
    else {
        if(sum - mx + v2[ptr].first <= k || sum + mn[ptr] <= k)return 2*ptr+1;
        else return 2*ptr;
    }
}

long long solve2(int n, long long k, int x, int y)
{
    dfs_path(x, y);
    long long re = 0;
    v1.clear();
    v2.clear();
    ptr = 0;
    mx = -INF;
    sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (onp[i])
        {
            k -= min(depX[i], depY[i]);
            vec1.clear();
            vec2.clear();
            long long inc = abs(depX[i] - depY[i]);
            dfs_gen(i, -1, inc);
            for(auto v: vec1){
                v1.push_back(v);
                v1.push_back(inc);
            }
            for(auto v: vec2){
                v2.push_back({v+inc, v});
            }
            // cout << i << endl;
            // for(auto v: knapsack[len])cout << v << " ";
            // cout << endl;
        }
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    if(!v2.empty()){
        mn.resize(v2.size());
        for(int i = v2.size() - 1; i >= 0; i--){
            mn[i] = v2[i].second;
            if(i + 1 < v2.size())mn[i] = min(mn[i], mn[i+1]);
        }
    }
    // cout << "left " << k << endl;
    if (k < 0)
        return 0;
    k -= accumulate(v1.begin(), v1.end(), 0LL);
    re = max(re, solve_v2(k) + (long long)v1.size());
    for(int i = v1.size() - 1; i >= 0; i--){
        k += v1[i];
        re = max(re, solve_v2(k) + i);
    }
    return re;
    
}
 
void reset(int n)
{
    for (int i = 0; i < n; i++)
    {
        g[i].clear();
        onp[i] = 0;
    }
    path.clear();
}
 
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    reset(N);
    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);
    dfsY(Y);
    long long ans = max(solve1(N, K), solve2(N, K, X, Y));
 
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < vec.size(); i++)
      |                     ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int solve_v2(long long int)':
closing.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     while(ptr < v2.size() && v2[ptr].first + sum <= k) {
      |           ~~~~^~~~~~~~~~~
closing.cpp:95:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     if(ptr == v2.size())return 2*ptr;
      |        ~~~~^~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             if(i + 1 < v2.size())mn[i] = min(mn[i], mn[i+1]);
      |                ~~~~~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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