oj.uz

Submission #847487

# Submission time Handle Problem Language Result Execution time Memory
847487 2023-09-09T18:05:10 Z nvmdava Closing Time (IOI23_closing) C++17
8 / 100
 1000 ms 38596 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200'005;

vector<pair<int, ll> > adj[N];

ll dx[N];
int px[N];
int py[N];
ll dy[N];

ll d[N];
int p[N];


void dfs(int v, int par) {
    p[v] = par;
    for(auto& u : adj[v]) {
        if(u.first == par) continue;
        d[u.first] = u.second + d[v];
        dfs(u.first, v);
    }
}


int max_score(int n, int X, int Y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for(int i = 0; i < n; ++i){
        d[i] = dx[i] = dy[i] = p[i] = px[i] = py[i] = 0;
        adj[i].clear();
    }
    for(int i = 0; i < n - 1; ++i) {
        adj[U[i]].push_back({V[i], W[i]});   
        adj[V[i]].push_back({U[i], W[i]});
    }
    dfs(X, -1);
    swap(d, dx);
    swap(p, px);

    dfs(Y, -1);
    swap(d, dy);
    swap(p, py);

    int res = 0;

    vector<ll> dd;
    for(int i = 0; i < n; ++i) dd.push_back(min(dx[i], dy[i]));
    sort(dd.begin(), dd.end());
    ll tmp = k;
    for(int i = 0; i < n; ++i) {
        tmp -= dd[i];
        if(tmp >= 0) res = i + 1;
    }
    
    int cur = 0;
    ll sum = 0;
    multiset<ll> q, w;
    // q - solo, w - double

    vector<pair<ll, ll> > help;

    for(int i = 0; i < n; ++i) {
        if(dx[i] + dy[i] == dx[Y]) {
            k -= min(dx[i], dy[i]);
            ++cur;
            q.insert(abs(dx[i] - dy[i]));
            if(k < 0) return res;
        } else {
            help.push_back({min(dx[i], dy[i]), max(dx[i], dy[i])});
            q.insert(min(dx[i], dy[i]));
        }
    }
    sort(help.begin(), help.end(), [](const pair<ll, ll>& lhs, const pair<ll, ll>& rhs) {
        return lhs.second - lhs.first == rhs.second - rhs.first ? lhs.first < rhs.first : lhs.second - lhs.first < rhs.second - rhs.first;
    });

    auto qit = q.begin();
    auto wit = w.begin();

    while(qit != q.end() && sum + *qit <= k) {
        ++cur;
        sum += *qit;
        ++qit;
    }

    res = max(res, cur);

    for(auto& e : help) {
        if(wit == w.end() || *wit > e.second) {
            cur += 2;
            sum += e.second;
        }
        w.insert(e.second);
        if(sum > k) {
            --wit;
            sum -= *wit;
            cur -= 2;
        }

        auto fin = q.find(e.first);
        if(qit == w.end() || *qit >= e.first) {
            cur -= 1;
            sum -= e.first;
        }
        if(qit == fin) {
            cur += 1;
            sum += e.first;
            ++qit;
        }
        q.erase(fin);

        bool reb = 0;
        do {
            while(qit != q.end() && sum + *qit <= k) {
                sum += *qit;
                cur += 2;
                qit++;
                reb = 1;
            }
            while(wit != w.end() && sum + *wit <= k) {
                sum += *wit;
                cur += 2;
                wit++;
                reb = 1;
            }
            if(wit != w.end() && qit != q.begin()) {
                auto q1 = qit;
                q1--;
                if(sum - *q1 + *wit <= k) {
                    sum += *wit - *q1;
                    ++cur;
                    --qit;
                    ++wit;
                    reb = 1;
                    continue;
                }
                if(q1 != q.begin()){
                    auto q2 = q1;
                    q2--;
                    if(*q1 + *q2 > *wit) {
                        sum += *wit;
                        ++wit;
                        sum -= *q1 + *q2;
                        --qit;
                        --qit;
                        reb = 1;
                        continue;
                    }
                }
            }
            if(wit != w.begin() && qit != q.end()) {
                auto q1 = qit;
                auto w1 = wit;
                w1--;
                q1++;
                if(q1 != q.end()) {
                    if(*qit + *q1 < *w1) {
                        reb = 1;
                        sum += *qit + *q1 - *w1;
                        wit--;
                        qit++;
                        qit++;
                        continue;
                    }
                }
            }
        } while(reb);
        res = max(res, cur);
    }

    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 33740 KB Output is correct
2 Correct 117 ms 38596 KB Output is correct
3 Correct 159 ms 14772 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 12120 KB Time limit exceeded
2 Halted 0 ms 0 KB -