Submission #851550

#	Time	Username	Problem	Language	Result	Execution time	Memory
851550		boris_mihov	Closing Time (IOI23_closing)	C++17	0 / 100	1022 ms	42508 KiB

closing

#include "closing.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 8e18;
const int INTINF = 2e9;

int n;
int x;
int y;
llong k;
llong distX[MAXN];
llong distY[MAXN];
std::vector <std::pair <llong,int>> toX; 
std::vector <std::pair <llong,int>> toY; 
std::vector <std::pair <llong,int>> toBoth; 
std::vector <std::pair <int,int>> g[MAXN];
bool shouldSkip[MAXN];
bool shouldBreak[MAXN];
int atLeastX[MAXN];
int atLeastY[MAXN];
int posX[MAXN];
int posY[MAXN];

std::vector <int> path;
void reset()
{
    path.clear();
    std::fill(distX, distX + n, 0);
    std::fill(distY, distY + n, 0);
    toX.clear(); toY.clear(); toBoth.clear();

    for (int i = 0 ; i < n ; ++i)
    {
        atLeastX[i + 1] = 0;
        atLeastY[i + 1] = 0;
        posX[i] = 0;
        posY[i] = 0;
        g[i].clear();
    }
}

void resetBL()
{
    std::fill(shouldSkip, shouldSkip + n, false);
    std::fill(shouldBreak, shouldBreak + n, false);
}

void dfs(int node, int par, llong to[], llong dist)
{
    to[node] = dist;
    for (const auto &[u, d] : g[node])
    {
        if (u == par)
        {
            continue;
        }

        dfs(u, node, to, dist + d);
    }
}

bool dfsPath(int node, int par)
{
    if (node == y)
    {
        path.push_back(node);
        return true;
    }

    for (const auto &[u, d] : g[node])
    {
        if (u == par)
        {
            continue;
        }

        if (dfsPath(u, node))
        {
            path.push_back(node);
            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)
{
    reset();
    n = N;
    x = X;
    y = Y;
    k = K;

    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, 0, distX, 0);
    dfs(y, 0, distY, 0);
    for (int i = 0 ; i < n ; ++i)
    {
        toX.push_back({distX[i], i});
        toY.push_back({distY[i], i});
        toBoth.push_back({std::max(distX[i], distY[i]), i});
    }

    std::sort(toX.begin(), toX.end());
    std::sort(toY.begin(), toY.end());
    std::sort(toBoth.begin(), toBoth.end());

    for (int i = 0 ; i < n ; ++i)
    {
        posX[toX[i].second] = i;
        posY[toY[i].second] = i;
    }

    dfsPath(x, 0);
    // std::cout << "path\n";
    // for (const auto &node : path)
    // {
    //     std::cout << node << ' ';
    // }

    // std::cout << '\n';
    int ptr = path.size() - 1;
    for (int i = n - 1 ; i > 0 ; --i)
    {
        atLeastX[i] = atLeastX[i + 1];
        if (ptr >= 0 && path[ptr] == toBoth[i].second)
        {
            atLeastX[i] = std::max(atLeastX[i], posX[toBoth[i].second] + 1);
            ptr--;
        }
    }

    ptr = path.size() - 1;
    std::reverse(path.begin(), path.end());
    for (int i = n - 1 ; i > 0 ; --i)
    {
        atLeastY[i] = atLeastY[i + 1];
        if (ptr >= 0 && path[ptr] == toBoth[i].second)
        {
            atLeastY[i] = std::max(atLeastY[i], posY[toBoth[i].second] + 1);
            ptr--;
        }
    }


    // std::cout << "both\n";
    // for (const auto &[dist, node] : toBoth)
    // {
    //     std::cout << node << ' ' << dist << '\n';
    // }

    // std::cout << "x\n";
    // for (const auto &[dist, node] : toX)
    // {
    //     std::cout << node << ' ' << dist << '\n';
    // }

    // std::cout << "y\n";
    // for (const auto &[dist, node] : toY)
    // {
    //     std::cout << node << ' ' << dist << '\n';
    // }

    // std::cout << "at leasts\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cout << i << ": " << atLeastX[i] << ' ' << atLeastY[i] << '\n';
    // }

    int ans = 0;
    for (int inBoth = 0 ; inBoth <= n ; ++inBoth)
    {
        for (int inX = atLeastX[inBoth] ; inX <= n ; ++inX)
        {
            for (int inY = atLeastY[inBoth] ; inY <= n ; ++inY)
            {
                resetBL();
                int res = 0;
                llong cost = 0;
                for (int i = 0 ; i < inBoth ; ++i)
                {
                    res += 2;
                    cost += toBoth[i].first;
                    shouldSkip[toBoth[i].second] = true;
                }

                for (int i = 0 ; i < inX ; ++i)
                {
                    if (shouldSkip[toX[i].second])
                    {
                        continue;
                    }

                    res++;
                    cost += toX[i].first;
                    shouldBreak[toX[i].second] = true;
                }

                for (int i = 0 ; i < inY ; ++i)
                {
                    if (shouldSkip[toY[i].second])
                    {
                        continue;
                    }

                    if (shouldSkip[toY[i].second])
                    {
                        cost = k + 1;
                        break;
                    }

                    res++;
                    cost += toY[i].first;                    
                }

                if (cost <= k)
                {
                    ans = std::max(ans, res);
                }
            }
        }
    }

    return ans;
}

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