oj.uz

Submission #851559

# Submission time Handle Problem Language Result Execution time Memory
851559 2023-09-20T06:46:41 Z boris_mihov Closing Time (IOI23_closing) C++17
17 / 100
 165 ms 39740 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 shouldBreak[MAXN];
llong applied[MAXN];
int atLeastX[MAXN];
int atLeastY[MAXN];
bool shouldSkip[MAXN];
bool reachableX[MAXN];
bool reachableY[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);
    std::fill(reachableX, reachableX + n, 0);
    std::fill(reachableY, reachableY + 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, -1, distX, 0);
    dfs(y, -1, distY, 0);
    resetBL();

    dfsPath(x, -1);
    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 && !reachableY[path[pos[node] - 1]]) neighGood = false;
        if (pos[node] + 1 < path.size() && !reachableX[path[pos[node] + 1]]) neighGood = false;

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

        if (type != 2 && k >= cost)
        {
            res++;
            k -= cost;
            applied[node] = cost;
            shouldSkip[node] = true;
            if (type == 0) reachableX[node] = true;
            if (type == 1) reachableY[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:138:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
closing.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         if (pos[node] + 1 < path.size() && !reachableX[path[pos[node] + 1]]) neighGood = false;
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 36840 KB Output is correct
2 Correct 164 ms 39740 KB Output is correct
3 Correct 75 ms 15188 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 3 ms 12632 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 3 ms 12632 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 3 ms 12632 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Correct 3 ms 12632 KB Output is correct
9 Incorrect 2 ms 12636 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 3 ms 12632 KB Output is correct
13 Correct 2 ms 12632 KB Output is correct
14 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 3 ms 12632 KB Output is correct
13 Correct 2 ms 12632 KB Output is correct
14 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 3 ms 12632 KB Output is correct
13 Correct 2 ms 12632 KB Output is correct
14 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 3 ms 12632 KB Output is correct
13 Correct 2 ms 12632 KB Output is correct
14 Incorrect 2 ms 12632 KB 1st lines differ - on the 1st token, expected: '18', found: '17'
15 Halted 0 ms 0 KB -