Submission #1065220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065220		becaido	Closing Time (IOI23_closing)	C++17	75 / 100	710 ms	565844 KiB

closing

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "closing.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 2e18;
const int SIZE = 3005;

int n, x, y, ans;
int sz[SIZE];
vector<pair<int, int>> adj[SIZE];
ll k, dx[SIZE], dy[SIZE], dp[SIZE][4][SIZE << 1], tmp[SIZE << 1];

void chmin(ll &x, ll y) {
    x = min(x, y);
}

void build(int s, ll *dis) {
    fill(dis + 1, dis + n + 1, INF);
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (auto [np, w] : adj[pos]) if (dis[pos] + w < dis[np]) {
            dis[np] = dis[pos] + w;
            q.push(np);
        }
    }
}

void merge(int sz1, int sz2, ll *a, ll *b) {
    FOR (i, 0, sz1) if (a[i] != INF) {
        FOR (j, 0, sz2) {
            chmin(tmp[i + j], a[i] + b[j]);
        }
    }
}

void dfs(int pos, int fa) {
    sz[pos] = 2;
    dp[pos][0][0] = 0;
    dp[pos][1][1] = dx[pos];
    dp[pos][2][1] = dy[pos];
    dp[pos][3][2] = max(dx[pos], dy[pos]);
    for (auto [np, w] : adj[pos]) if (np != fa) {
        dfs(np, pos);
        int tsz = sz[pos] + sz[np];

        fill(tmp, tmp + tsz + 1, INF);
        merge(sz[pos], sz[np], dp[pos][0], dp[np][0]);
        if (dy[np] < dy[pos]) merge(sz[pos], sz[np], dp[pos][0], dp[np][2]);
        FOR (i, 0, tsz) chmin(dp[pos][0][i], tmp[i]);

        fill(tmp, tmp + tsz + 1, INF);
        merge(sz[pos], sz[np], dp[pos][1], dp[np][0]);
        merge(sz[pos], sz[np], dp[pos][1], dp[np][1]);
        if (dy[np] < dy[pos]) {
            merge(sz[pos], sz[np], dp[pos][1], dp[np][2]);
            merge(sz[pos], sz[np], dp[pos][1], dp[np][3]);
        }
        FOR (i, 0, tsz) chmin(dp[pos][1][i], tmp[i]);

        if (dy[np] < dy[pos]) {
            fill(tmp, tmp + tsz + 1, INF);
            merge(sz[pos], sz[np], dp[pos][2], dp[np][2]);
            FOR (i, 0, tsz) dp[pos][2][i] = tmp[i];

            fill(tmp, tmp + tsz + 1, INF);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][2]);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][3]);
            FOR (i, 0, tsz) dp[pos][3][i] = tmp[i];
        } else {
            fill(tmp, tmp + tsz + 1, INF);
            merge(sz[pos], sz[np], dp[pos][2], dp[np][0]);
            merge(sz[pos], sz[np], dp[pos][2], dp[np][2]);
            FOR (i, 0, tsz) chmin(dp[pos][2][i], tmp[i]);

            fill(tmp, tmp + tsz + 1, INF);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][0]);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][1]);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][2]);
            merge(sz[pos], sz[np], dp[pos][3], dp[np][3]);
            FOR (i, 0, tsz) chmin(dp[pos][3][i], tmp[i]);
        }

        sz[pos] = tsz;
    }
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    n = N, x = X + 1, y = Y + 1, k = K;
    FOR (i, 1, n) adj[i].clear();
    FOR (i, 0, n - 2) {
        U[i]++, V[i]++;
        adj[U[i]].pb(V[i], W[i]);
        adj[V[i]].pb(U[i], W[i]);
    }
    FOR (i, 1, n) FOR (mask, 0, 3) fill(dp[i][mask], dp[i][mask] + 2 * n + 1, INF);
    build(x, dx), build(y, dy);
    dfs(x, x);
    ans = 0;
    FOR (j, 0, 2 * n) FOR (i, 0, 3) if (dp[x][i][j] <= k) ans = j;
    return ans;
}

/*
in1
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19
out1
6
3
*/

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