The 2025 ICPC Asia East Continent Online Contest (I)

A. Who Can Win

模拟题。把 submission 按时间排序后，对每个队伍保存 solved 数、罚时、reject 数、unknown 数。接着按 $\tt{(solved, penalty)}$ 排序，然后检查队伍 $i$ 是否可以夺冠，就令他们所有的题目都通过，并且所有其他队伍都没通过，然后和目前的冠军比较一下即可。

实现的时候需要注意计入 penalty 的条件. 时间复杂度 $O(n\log n)$

AC Code

#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int P = 30, N = 1e5 + 10;
using ll = long long;

struct team {
    std::string name;
    std::array<int, P> ac, un, rej;
    ll penalty, solved;

    team() {
        ac.fill(-1), un.fill(-1), rej.fill(0);
        penalty = 0, solved = 0;
    }
};
struct record {
    std::string name, verdict;
    int time;
    int problem;
} r[N];
std::map<std::string, team> contest;

int n;

void Run() {
    std::cin >> n;
    contest.clear();

    repeat(i, 1, n) {
        char f;
        std::cin >> r[i].name >> f >> r[i].time >> r[i].verdict;
        r[i].problem = f - 'A';
        team t = team();
        t.name = r[i].name;
        contest.insert({r[i].name, t});
    }
    std::sort(range(r, 1, n), [](record &a, record &b) { return a.time < b.time; });

    repeat(i, 1, n) {
        auto [name, verdict, time, prob] = r[i];
        if (verdict == "Accepted") {
            if (contest[name].ac[prob] == -1) {
                contest[name].ac[prob] = time;
                contest[name].penalty += time;
                contest[name].penalty += 20 * contest[name].rej[prob];
                contest[name].solved++;
            }
        } else if (verdict == "Rejected") {
            if (contest[name].ac[prob] == -1) contest[name].rej[prob]++;
        } else {
            if (contest[name].ac[prob] == -1 && contest[name].un[prob] == -1) contest[name].un[prob] = time;
        }
    }

    std::vector<team> v;
    for (auto &[x, y] : contest) v.push_back(y);

    std::sort(all(v), [](team &a, team &b) { return a.solved == b.solved ? a.penalty < b.penalty : a.solved > b.solved; });

    ll championT = v[0].penalty, championP = v[0].solved;

    std::vector<std::string> ans;
    for (auto &t : v) {
        repeat(i, 0, 25) {
            if (t.un[i] != -1) t.solved++, t.penalty += t.un[i] + 20 * t.rej[i];
        }

        if (t.solved > championP) ans.push_back(t.name);
        else if (t.solved == championP && t.penalty <= championT) ans.push_back(t.name);
    }

    std::sort(all(ans));
    for (auto &s : ans) std::cout << s << " ";
    std::cout << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

B. Creating Chaos

结论是只要取 $1,2,\dots, k$ 就一定是最优的。证明待补（

AC Code

#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

void Run() {
    int n, k;
    std::cin >> n >> k;
    repeat(i, n - k + 1, n) std::cout << i << " \n"[i == n];
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) Run();
}

G. Sorting

考虑 $a_i=i+1,a_{i+1}=i$ 的情况，此时，若 $i,i+1$ 之间没有连边，那么永远无法通过 $k\ne i, k\ne i+1$ 将这两个数交换过来。

所以充要条件是对 $i\in [1,n-1]$ ， $(i,i+1)$ 有连边。时间复杂度 $O(n)$

AC Code

#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;

int n, m;
int a[N], b[N];
int mark[N];

void Run() {
    std::cin >> n >> m;
    repeat(i, 1, n) mark[i] = 0;
    repeat(i, 1, m) {
        std::cin >> a[i] >> b[i];
        if (b[i] == a[i] + 1) mark[a[i]] = 1;
    }

    int t = 0;
    repeat(i, 1, n - 1) t += mark[i];
    std::cout << (t == n - 1 ? "Yes" : "No") << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) Run();
}

I. Knapsack Problem

一个很关键的点：给定序列 $\set{a_i}$ 用大小为 $V$ 的背包顺序或逆序的把所有数放进去，则无论顺序还是逆序，使用的背包数量是相同的.

所以这道题就变成了 Dijkstra 的变体：我们在每个节点上维护

使用的背包数量（越少越好）
当前背包的剩余容量（越多越好）

然后把这个东西当作 $\tt{dist}$ 跑 Dijkstra 即可。时间复杂度 $O(n\log n)$

AC Code

#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int inf = 1e9;

struct edge {
    int u, v, w;
} E[N];

int n, m, V, T;
vi G[N];

pii dist[N];
int fa[N], vis[N];

int endpoint(edge e, int u) { return e.u + e.v - u; }

void Run() {
    std::cin >> n >> m >> V >> T;
    repeat(i, 1, m) {
        std::cin >> E[i].u >> E[i].v >> E[i].w;
        G[E[i].u].push_back(i);
        G[E[i].v].push_back(i);
    }
    repeat(i, 1, n) dist[i] = {inf, 0};
    [&] {
        dist[T] = {1, V};
        using node = std::pair<pii, int>;
        auto f = [&](node a, node b) -> bool {
            return !(a.first.first == b.first.first 
                        ? a.first.second > b.first.second 
                        : a.first.first < b.first.first);
        };
        std::priority_queue<node, std::vector<node>, decltype(f)> pq(f);
        pq.push({{1, V}, T});

        while (!pq.empty()) {
            auto [D, u] = pq.top();
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;

            for (auto eid : G[u]) {
                int v = endpoint(E[eid], u), w = E[eid].w;

                pii nd = dist[u];
                if (nd.second < w) nd.first++, nd.second = V - w;
                else nd.second -= w;

                if (f(node{dist[v], v}, node{nd, u})) {
                    dist[v] = nd;
                    pq.push({nd, v});
                }
            }
        }
    }();

    repeat(i, 1, n) 
        std::cout << (dist[i].first == inf ? -1 : dist[i].first) << " \n"[i == n];
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) Run();
}

M. Teleporter

首先可以看出来是个分层图。但是我们不能直接把全图建出来跑 dijkstra，这样的话一共会有 $O(n^2+mn)$ 条边，跑 Dijkstra 很容易爆。

所以我们手动在层与层之间更新 $\tt{dist}$ ：

第 $0$ 层我们随便跑一个 DFS；
从第 $k$ 层推到第 $k+1$ 层，我们先处理 teleport.
然后对于那些“使用 teleport 可以减少 dist”的点，我们把他们加入 dijkstra 的堆中
在当前层跑一次 Dijkstra

第 $0$ 层的 DFS 是 $O(n)$ 的（虽然我写成了 $O(n^2)$ 但是无伤大雅）；从上一层推到下一层首先需要 $O(m)$ 处理 teleport，然后会在树上跑 Dijkstra，有 $O(n)$ 条边，所以每一层的转移是 $O(m+n\log n)$ 的。由于一共要处理 $n$ 层，所以总的时间复杂度是 $O(nm+n^2\log n)$

AC Code

#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;

constexpr int N = 5005;
constexpr ll inf = 1e18;

int n, m;
std::vector<pli> G[N], H[N];
ll map[N][N], dp[N][N];

void Run() {
    std::cin >> n >> m;
    repeat(i, 1, n - 1) {
        int u, v, w;
        std::cin >> u >> v >> w;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }
    repeat(i, 1, m) {
        int u, v;
        std::cin >> u >> v;
        H[u].push_back({0, v});
        H[v].push_back({0, u});
    }
    auto source = [&](int s) {
        repeat(i, 1, n) map[s][i] = inf;
        map[s][s] = 0;

        auto dfs = [&](auto F, int u, int fa) -> void {
            for (auto [w, v] : G[u]) {
                if (v == fa) continue;
                map[s][v] = map[s][u] + w;
                F(F, v, u);
            }
        };
        dfs(dfs, s, s);
    };
    repeat(i, 1, n) source(i);
    ll sum = 0;
    repeat(i, 1, n) {
        dp[0][i] = map[1][i];
        sum += dp[0][i];
    }
    std::cout << sum << "\n";

    repeat(depth, 1, n) {
        ll sum = 0;
        repeat(i, 1, n) dp[depth][i] = dp[depth - 1][i];
        using node = std::pair<ll, int>;
        std::priority_queue<node, std::vector<node>, std::greater<node>> q;
        repeat(u, 1, n) for (auto [w, v] : H[u]) {
            if (dp[depth][v] > dp[depth - 1][u]) {
                dp[depth][v] = dp[depth - 1][u];
                q.push({dp[depth][v], v});
            }
        }

        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();

            if (dp[depth][u] < d) continue;
            for (auto [w, v] : G[u]) {
                if (dp[depth][v] > dp[depth][u] + w) {
                    dp[depth][v] = dp[depth][u] + w;
                    q.push({dp[depth][v], v});
                }
            }
        }

        repeat(i, 1, n) sum += dp[depth][i];
        std::cout << sum << "\n";
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) Run();
}