oj.uz

답안 #851550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851550 2023-09-20T06:15:04 Z boris_mihov 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 1000 ms 42508 KB 
#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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1022 ms 42508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 3 ms 10584 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -