Submission #1008930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008930		12345678	Closing Time (IOI23_closing)	C++17	30 / 100	1050 ms	38080 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#pragma gcc-optimize("O3, unrolls-loops")

const int nx=2e5+5;

vector<pair<ll, ll>> g[nx];

void dfs(int u, int p, ll cw, vector<ll> &pa, vector<ll> &x)
{
    pa[u]=p;
    x[u]=cw;
    for (auto [v, w]:g[u]) if (v!=p) dfs(v, u, cw+w, pa, x);
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    ll mx=0;
    for (int i=0; i<N; i++) g[i].clear();
    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]});
    vector<ll> pa(N), pb(N), a(N), b(N);
    dfs(X, X, 0, pa, a);
    dfs(Y, Y, 0, pb, b);
    priority_queue<ll, vector<ll>, greater<ll>> pq2;
    for (int i=0; i<N; i++) pq2.push(a[i]), pq2.push(b[i]);
    ll tmp=K;
    while (!pq2.empty()&&pq2.top()<=tmp) mx++, tmp-=pq2.top(), pq2.pop();
    vector<ll> path;
    tmp=Y;
    while (tmp!=X) path.push_back(tmp), tmp=pa[tmp];
    path.push_back(X);
    reverse(path.begin(), path.end());
    ll sz=path.size();
    for (int i=0; i<sz; i++)
    {
        for (int j=i; j<sz; j++)
        {
            ll c=K, res=0;
            priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
            vector<ll> vs(N);
            for (int k=i; k<=j; k++) vs[path[k]]=1, c-=max(a[path[k]], b[path[k]]), res+=2;
            for (int k=0; k<i; k++) vs[path[k]]=1, res++, c-=a[path[k]];
            for (int k=j+1; k<sz; k++) vs[path[k]]=1, res++, c-=b[path[k]];
            for (int k=i; k<=j; k++) for (auto [v, w]:g[path[k]]) if (!vs[v]) pq.push({max(a[v], b[v]), v});
            if (c<0) continue;
            while (!pq2.empty()) pq2.pop();
            for (int i=0; i<N; i++) if (!vs[i]) pq2.push(a[i]), pq2.push(b[i]);
            ll tmpres=res, tmpc=c;
            while (!pq2.empty()&&tmpc>=pq2.top()) tmpres++, tmpc-=pq2.top(), pq2.pop();
            mx=max(mx, tmpres);
            while (!pq.empty())
            {
                auto [w, u]=pq.top();
                pq.pop();
                c-=w;
                vs[u]=1;
                res+=2;
                for (auto [v, cw]:g[u]) if (!vs[v]) pq.push({max(a[v], b[v]), v});
                if (c<0) continue;
                while (!pq2.empty()) pq2.pop();
                for (int i=0; i<N; i++) if (!vs[i]) pq2.push(a[i]), pq2.push(b[i]);
                tmpres=res, tmpc=c;
                while (!pq2.empty()&&tmpc>=pq2.top()) tmpres++, tmpc-=pq2.top(), pq2.pop();
                mx=max(mx, tmpres);
            }
        }
    }
    return mx;
}

/*
1
6 0 3 20
0 1 2
1 2 5
2 3 6
1 4 5
1 5 2
*/

Compilation message (stderr)

closing.cpp:7: warning: ignoring '#pragma gcc ' [-Wunknown-pragmas]
    7 | #pragma gcc-optimize("O3, unrolls-loops")
      |

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17