Submission #1251826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251826		antonn	World Map (IOI25_worldmap)	C++20	72 / 100	111 ms	9580 KiB

worldmap

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

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int n, m;
vector<vector<int>> g, neigh, full;
vector<int> t, sz;

int root(int x) {
    if (t[x] == x) {
        return x;
    }
    return t[x] = root(t[x]);
}

void join(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
        return;
    }
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    t[b] = a;
    sz[a] += sz[b];
}

vector<vector<int>> c;

void solve(int u, vector<int> kids) {
    vector<int> l;
    l.push_back(u);
    for (auto v : kids) {
        l.push_back(v);
        l.push_back(u);
    }
    c.push_back(l);
}

void dfs(int u, int p = 0) {
    c.push_back({u});
    solve(u, full[u]);
    c.push_back({u});
    for (auto v : g[u]) {
        if (v != p) {
            dfs(v, u);
            c.push_back({u});
        }
    }
}

vector<vector<int>> reshape(vector<vector<int>> c) {
    int k = c.size();
    for (int i = 0; i < c.size(); i++) {
        k = max(k, (int) c[i].size());
    }
    for (int i = 0; i < c.size(); i++) {
        while (c[i].size() < k) {
            c[i].push_back(c[i].back());
        }
    }
    while (c.size() < k) {
        c.push_back(c.back());
    }
    return c;
}

vector<vector<int>> create_map(int N, int M, vector<int> a, vector<int> b) {
    n = N;
    m = M;
    c.clear();
    g.assign(n + 1, {});
    t.resize(n + 1);
    sz.resize(n + 1);
    full.assign(n + 1, {});
    for (int i = 1; i <= n; i++) {
        t[i] = i;
        sz[i] = 1;
    }
    neigh.assign(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        full[a[i]].push_back(b[i]);
        full[b[i]].push_back(a[i]);
        neigh[a[i]][b[i]] = neigh[b[i]][a[i]] = 1;
        if (root(a[i]) == root(b[i])) {
            continue;
        }
        join(a[i], b[i]);
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(1);
    assert(c.size() <= 4 * n);
    return reshape(c);
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 28 / 56