제출 #843651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843651		Boas	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	1065 ms	38104 KiB

closing

#include "closing.h"

#include <vector>
using namespace std;
#include <bits/stdc++.h>

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef vector<sii> vsii;
typedef tuple<int, int, int, bool> item;

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

typedef long long ll;
void getDist(int i, int 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, vi U, vi V, vi 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 max = 0;
    ll K1 = 0;
    for (int xleft = 0; X - xleft >= 0; xleft++)
    {
        ll K2 = 0;
        for (int xright = 0; X + xright < N; xright++)
        {
            ll K3 = 0;
            for (int yleft = 0; yleft <= Y; yleft++)
            {
                ll sum = K1 + K2 + K3;
                int yright = 0;
                for (; Y + yright < N; yright++)
                {
                    ll nieuw = sum + distY[Y + yright];
                    if (K - nieuw >= 0)
                        sum = nieuw;
                }
                if (K - sum < 0)
                    break;
                int count = 2 + xright + yright + xleft + yleft;
                if (count > max)
                {
                    cerr << "Solution has: " << xleft << ' ' << xright << ' ' << yleft << ' ' << yright << endl;
                    max = count;
                }
                if (X + xright >= Y - yleft)
                {
                    K3 += std::max(distY[Y - yleft], distX[Y - yleft]);
                    K3 -= std::min(distY[Y - yleft], distX[Y - yleft]);
                }
                else
                {
                    K3 += distY[Y - yleft];
                }
            }
            K2 += distX[X + xright];
        }
        K1 += distX[X - xleft];
    }
    cerr << endl;
    return max;
}

• 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