Submission #1252289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252289		EJIC_B_KEDAX	World Map (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

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

using namespace std;
using ll = long long;

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        a[i]--; b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    int K = 2 * n;
    vector<vector<int>> ans(K, vector<int>(K, -1));
    vector<int> used(n, 0), tin(n), sz(n);
    int cur = 0, timer = 0;
    auto dfs = [&](auto dfs, int s) -> void {
        used[s] = 1;
        tin[s] = timer++;
        sz[s] = 1;
        vector<int> rememb = {cur};
        cur++;
        vector<int> chld;
        int cnt = 0;
        for (int i : g[s]) {
            if (!used[i]) {
                cnt++;
                dfs(dfs, i);
                sz[s] += sz[i];
                rememb.push_back(cur);
                cur++;
            } else if (tin[i] > tin[s]) {
                chld.push_back(i);
            }
        }
        for (int i = rememb[0]; i <= rememb.back(); i++) {
            for (int j = 0; j < 2 * sz[s]; j++) {
                if (ans[i][j] == -1) {
                    ans[i][j] = s + 1;
                }
            }
        }
        if (cnt > 1) {
            for (int i = 0; i < chld.size(); i++) {
                ans[rememb[0] + 1 + 2 * i][2 * sz[s] - 2] = chld[i] + 1;
            }
        } else {
            for (int i = 0; i < chld.size(); i++) {
                ans[rememb[0] + 1 + 2 * i][2 * sz[s] - 2] = chld[i] + 1;
                ans[rememb[0] + 1 + 2 * i][2 * sz[s] - 3] = s + 1;
            }
        }
    };
    dfs(dfs, 0);
    for (; cur < K; cur++) {
        ans[cur] = ans[cur - 1];
    }
    return ans;
}

• 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: 56 / 56