oj.uz

Submission #840129

# Submission time Handle Problem Language Result Execution time Memory
840129 2023-08-31T07:05:25 Z socpite Closing Time (IOI23_closing) C++17
8 / 100
 163 ms 47308 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 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;
vector<long long> knapsack[maxn];
int mark[maxn];

bool chk(pair<int, int> a)
{
    return a.second < mark[a.first];
}

long long tval(pair<int, int> a)
{
    if (chk(a))
        return knapsack[a.first][a.second];
    else
        return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}

long long eval(pair<int, int> a)
{
    if (chk(a))
        return knapsack[a.first][a.second] * 2;
    else
        return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}

struct cmp
{
    bool operator()(const pair<int, int> a, const pair<int, int> b) const
    {
        return eval(a) > eval(b);
    }
};

long long brute(priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq, pair<int, int> val, long long k) {
    auto old_pq = pq;
    long long ans1 = 0, ans2 = 0, old_k = k;
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        if(k >= tval(x))k-=tval(x);
        else {
            if(k >= knapsack[x.first][x.second])ans1++;
            break;
        }
        ans1+=2;
    }
    pq = old_pq;
    k = old_k;
    if(k >= tval(val)){
        k -= tval(val);
        ans2++;
        for(int i = mark[val.first]; i < knapsack[val.first].size(); i+=2) {
            pq.push({val.first, i});
        }
        while(!pq.empty()){
            auto x = pq.top();
            pq.pop();
            if(k >= tval(x))k-=tval(x);
            else {
                if(k >= knapsack[x.first][x.second])ans2++;
                break;
            }
            ans2+=2;
        }
    }
    return max(ans1, ans2);

}

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);
    }
}


long long solve2(int n, long long k, int x, int y)
{
    dfs_path(x, y);
    int len = 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);
            sort(vec1.begin(), vec1.end());
            sort(vec2.begin(), vec2.end());
            knapsack[len] = vec1;
            for (auto v : vec1)
                knapsack[len].push_back(inc);
            mark[len] = knapsack[len].size();
            for (auto v : vec2)
            {
                knapsack[len].push_back(v);
                knapsack[len].push_back(inc);
            }
            len++;
            // cout << i << endl;
            // for(auto v: knapsack[len])cout << v << " ";
            // cout << endl;
        }
    }
    // cout << "left " << k << endl;
    if (k < 0)
        return 0;
    long long re = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq2;
    for (int i = 0; i < len; i++){
        for(int j = 0; j < mark[i]; j++)pq1.push({i, j});
    }
    while(!pq1.empty() || !pq2.empty()) {
        if(pq1.empty()){
            auto x = pq2.top();
            pq2.pop();
            if(k >= tval(x))k -= tval(x);
            else {
                if(k >= knapsack[x.first][x.second]){
                    re++;
                }
                break;
            }
            re += 2;
        }
        else if(pq2.empty()){
            auto x = pq1.top();
            pq1.pop();
            if(x.second + 1 == mark[x.first]){
                for(int i = mark[x.first]; i < knapsack[x.first].size(); i+=2)pq2.push({x.first, i});
            }
            if(k >= tval(x))k -= tval(x);
            else break;
            re++;
        }
        else {
            auto pval = pq2.top();
            pq2.pop();
            auto val1 = pq1.top();
            pq1.pop();
            if(pq1.empty()){
                return re + brute(pq2, val1, k);
            }
            else {
                auto val2 = pq1.top();
                pq1.pop();
                if(tval(pval) < tval(val1) + tval(val2)){
                    if(k >= tval(pval)){
                        pq1.push(val1);
                        pq1.push(val2);
                        k -= tval(pval);
                        re += 2;
                    }
                    else {
                        pq2.push(pval);
                        return re + brute(pq2, val1, k);
                    }
                }
                else {
                    if(k >= tval(val1) + tval(val2)){
                        if(val1.second + 1 == mark[val1.first]){
                            for(int i = mark[val1.first]; i < knapsack[val1.first].size(); i+=2)pq2.push({val1.first, i});
                        }
                        if(val2.second + 1 == mark[val2.first]){
                            for(int i = mark[val2.first]; i < knapsack[val2.first].size(); i+=2)pq2.push({val2.first, i});
                        }
                        pq2.push(pval);
                        k -= tval(val1) + tval(val2);
                        re += 2;
                    }
                    else {
                        pq2.push(pval);
                        return re + brute(pq2, val1, k);
                    }
                }
            }
        }
    }

    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

closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < vec.size(); i++)
      |                     ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int brute(std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp>, std::pair<int, int>, long long int)':
closing.cpp:117:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i = mark[val.first]; i < knapsack[val.first].size(); i+=2) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:171:23: warning: unused variable 'v' [-Wunused-variable]
  171 |             for (auto v : vec1)
      |                       ^
closing.cpp:211:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |                 for(int i = mark[x.first]; i < knapsack[x.first].size(); i+=2)pq2.push({x.first, i});
      |                                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:243:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |                             for(int i = mark[val1.first]; i < knapsack[val1.first].size(); i+=2)pq2.push({val1.first, i});
      |                                                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:246:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |                             for(int i = mark[val2.first]; i < knapsack[val2.first].size(); i+=2)pq2.push({val2.first, i});
      |                                                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 40452 KB Output is correct
2 Correct 163 ms 47308 KB Output is correct
3 Correct 74 ms 12452 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Incorrect 4 ms 9684 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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Incorrect 4 ms 9684 KB 1st lines differ - on the 1st token, expected: '96', found: '108'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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