Submission #1008456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008456		12345678	Closing Time (IOI23_closing)	C++17	0 / 100	1055 ms	47296 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);
    for (int i=0; i<(1<<N); i++)
    {
        ll cst=0, res=0;
        vector<int> vsa(N), vsb(N);
        for (int j=0; j<N; j++) 
        {
            if (i&(1<<j))
            {
                vsa[j]=vsb[j]=1;
                cst+=max(a[j], b[j]);
                res+=2;
                int tmp=j;
                while (tmp!=X)
                {
                    if (!vsa[tmp]) vsa[tmp]=1, res++, cst+=a[tmp];
                    tmp=pa[tmp];
                }
                tmp=j;
                while (tmp!=Y)
                {
                    if (!vsb[tmp]) vsb[tmp]=1, res++, cst+=b[tmp];
                    tmp=pb[tmp];
                }
            }
        }
        if (cst>K) continue; 
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        for (int i=0; i<N; i++) if (!vsa[i]) pq.push(a[i]);
        for (int i=0; i<N; i++) if (!vsb[i]) pq.push(b[i]);
        while (!pq.empty()&&cst+pq.top()<=K) res++, cst+=pq.top(), pq.pop();
        mx=max(mx, res);
    }
    return mx;
}

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: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17