oj.uz

Submission #851553

# Submission time Handle Problem Language Result Execution time Memory
851553 2023-09-20T06:35:29 Z boris_mihov Closing Time (IOI23_closing) C++17
8 / 100
 162 ms 43752 KB 
#include "closing.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

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];
llong applied[MAXN];
int atLeastX[MAXN];
int atLeastY[MAXN];
int pos[MAXN];

struct Element
{
    llong cost;
    int type;
    int node;

    friend bool operator < (const Element &a, const Element &b)
    {
        if (a.cost != b.cost) return a.cost > b.cost;
        if (a.type != b.type) return a.type > b.type;
        return a.node < b.node;
    }     
};

std::priority_queue <Element> pq;
std::vector <int> path;

void reset()
{
    while (!pq.empty())
    {
        pq.pop();
    }

    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)
    {
        applied[i] = 0;
        atLeastX[i + 1] = 0;
        atLeastY[i + 1] = 0;
        pos[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);
    resetBL();

    dfsPath(x, 0);
    for (int i = 0 ; i < path.size() ; ++i)
    {
        pos[path[i]] = i; 
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (distX[i] <= distY[i])
        {
            pq.push({distX[i], 0, i});
            pq.push({distY[i], 2, i});
        } else
        {
            pq.push({distY[i], 1, i});
            pq.push({distX[i], 2, i});
        }
    }

    int res = 0;
    while (!pq.empty())
    {
        auto [cost, type, node] = pq.top();
        pq.pop();

        bool neighGood = true;
        if (!shouldSkip[node]) neighGood = false;
        if (pos[node] > 0 && !shouldSkip[path[pos[node] - 1]]) neighGood = false;
        if (pos[node] + 1 < path.size() && !shouldSkip[path[pos[node] + 1]]) neighGood = false;

        if (type == 2 && neighGood && k >= cost - applied[node])
        {
            res++;
            k -= cost - applied[node];
        }

        if (type != 2 && k >= cost)
        {
            res++;
            k -= cost;
            applied[node] = cost;
            shouldSkip[node] = true;
        }
    }

    return res;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
closing.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         if (pos[node] + 1 < path.size() && !shouldSkip[path[pos[node] + 1]]) neighGood = false;
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 38148 KB Output is correct
2 Correct 157 ms 43752 KB Output is correct
3 Correct 81 ms 15848 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 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 1 ms 8540 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 1 ms 8540 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 10588 KB Output is correct
2 Incorrect 1 ms 8540 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 10588 KB Output is correct
2 Incorrect 1 ms 8540 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 10588 KB Output is correct
2 Incorrect 1 ms 8540 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 10588 KB Output is correct
2 Incorrect 1 ms 8540 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 10588 KB Output is correct
2 Incorrect 1 ms 8540 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
3 Halted 0 ms 0 KB -