Submission #1223644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223644		LucaIlie	Closing Time (IOI23_closing)	C++17	8 / 100	155 ms	55892 KiB

closing

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

using namespace std;

struct edge {
    int u, v, c;

    int other(int x) {
        return u ^ v ^ x;
    }
};

struct aaa {
    int t, v;
    long long c;

    bool operator < (const aaa &x) const {
        return x.c < c;
    }
};

struct aa {
    long long c;
    int v;
};

const int MAX_N = 2e5;
const long long INF = 1e18;
edge edges[MAX_N];
vector<int> adj[MAX_N];
int parent[MAX_N];
vector<int> path;
vector<int> subtree[MAX_N];
bool onPath[MAX_N], used[MAX_N];
int level[MAX_N];
long long dp[2 * MAX_N + 1];
long long distX[MAX_N], distY[MAX_N];
long long cost1[MAX_N], upgrade[MAX_N];
long long paid[MAX_N];
vector<aa> orderedByCost1, orderedByCost2;

void calcDist(int u, int p, long long dist[]) {
    // printf("aa %d %d %lld\n", u, p, dist[u]);
    parent[u] = p;
    for (int e: adj[u]) {
        int v = edges[e].other(u), c = edges[e].c;
        if (v == p)
            continue;
        dist[v] = dist[u] + c;
        calcDist(v, u, dist);
    }
}

void findSubtree(int u, int p, int w) {
    subtree[w].push_back(u);
    for (int e: adj[u]) {
        int v = edges[e].other(u);
        if (v == p || onPath[v])
            continue;
        findSubtree(v, u, w);
    }
}

int max_score(int n, int x, int y, long long k, 
                vector<int> U, vector<int> V, vector<int> W) {

    for (int v = 0; v < n; v++) {
        adj[v].clear();
        subtree[v].clear();
        parent[v] = 0;
        distX[v] = distY[v] = 0;
        onPath[v] = false;
        path.clear();
    }
    for (int e = 0; e < n - 1; e++) {
        adj[U[e]].push_back(e);
        adj[V[e]].push_back(e);
        edges[e] = {U[e], V[e], W[e]};
    }

    calcDist(x, -1, distX);
    calcDist(y, -1, distY);

    int v = x;
    while (v != y) {
        path.push_back(v);
        onPath[v] = true;
        v = parent[v];
    }
    path.push_back(y);
    onPath[y] = true;
    int m = path.size();

    for (int v = 0; v < n; v++) {
        cost1[v] = min(distX[v], distY[v]);
        upgrade[v] = max(distX[v], distY[v]) - cost1[v];
    }

    for (int i = 0; i < m; i++)
        findSubtree(path[i], -1, path[i]);

    for (int i = 0; i < n; i++)
        orderedByCost1.push_back({cost1[i], i});

    sort(orderedByCost1.begin(), orderedByCost1.end(), [](aa x, aa y) {return x.c < y.c;});

    int maxScore = 0;
    long long c = 0;
    while (maxScore < (int)orderedByCost1.size() && c + orderedByCost1[maxScore].c <= k) {
        c += orderedByCost1[maxScore].c;
        maxScore++;
    }

    long long cc = 0;
    for (int v = 0; v < n; v++) {
        if (onPath[v]) {
            orderedByCost1.push_back({upgrade[v], v});
            cc += cost1[v];
        } else
            orderedByCost2.push_back({cost1[v] + upgrade[v], v});
    }

    sort(orderedByCost1.begin(), orderedByCost1.end(), [](aa x, aa y) {return x.c < y.c;});
    sort(orderedByCost2.begin(), orderedByCost2.end(), [](aa x, aa y) {return x.c < y.c;});

    for (int t = 0; t < (int)orderedByCost2.size(); t++) {
        used[orderedByCost2[t].v] = true;
        cc += orderedByCost2[t].c;
        if (cc > k)
            continue;

        long long c = cc;
        int score = path.size() + t + 1;
        for (int o = 0; o < (int)orderedByCost1.size(); o++) {
            if (used[orderedByCost1[o].v])
                continue;

            if (c + orderedByCost1[o].c <= k) {
                c += orderedByCost1[o].c;
                score++;
            }
        }

        maxScore = max(maxScore, score);
    }

    for (int v = 0; v < n; v++) {
        adj[v].clear();
        subtree[v].clear();
        parent[v] = 0;
        distX[v] = distY[v] = 0;
        onPath[v] = used[v] = false;
        path.clear();
        orderedByCost1.clear();
        orderedByCost2.clear();
    }

    return maxScore;
}

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