Submission #966152

#	Time	Username	Problem	Language	Result	Execution time	Memory
966152		Boas	봉쇄 시간 (IOI23_closing)	C++17	9 / 100	1061 ms	45924 KiB

closing

#include "closing.h"
using namespace std;
#include <bits/stdc++.h>
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef vector<sii> vsii;
typedef tuple<ll, ll, ll, bool> item;

#define ALL(x) (x).begin(), x.end()
#define loop(x, i) for (int i = 0; i < x; i++)

void getDist(int i, ll d, vi &dist, const vsii &adj)
{
    dist[i] = d;
    for (auto [j, w] : adj[i])
    {
        if (dist[j] != -1)
            continue;
        getDist(j, dist[i] + w, dist, adj);
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    vsii adj(N);
    loop(N - 1, i)
    {
        adj[U[i]].insert({V[i], W[i]});
        adj[V[i]].insert({U[i], W[i]});
    }
    vi distX(N, -1), distY(N, -1);
    distX[X] = 0;
    distY[Y] = 0;
    getDist(X, 0, distX, adj);
    getDist(Y, 0, distY, adj);
    int res = 0;
    vb visX(N);
    vb visY(N);
    for (int xleft = X; xleft >= 0; xleft--)
    {
        for (int xright = X; xright < N; xright++)
        {
            for (int yleft = Y; yleft >= 0; yleft--)
            {
                for (int yright = Y; yright < N; yright++)
                {
                    ll sum = 0;
                    for (int p = 0; p < N; p++)
                    {
                        ll v = 0;
                        if (xleft <= p && p <= xright)
                            v = max(v, distX[p]);
                        if (yleft <= p && p <= yright)
                            v = max(v, distY[p]);
                        sum += v;
                    }
                    if (sum <= K)
                    {
                        res = max(res, 2 + yright + xright - xleft - yleft);
                    }
                }
            }
        }
    }
    cerr << endl;
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 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