Submission #1253407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253407		dreamnguyen	World Map (IOI25_worldmap)	C++20	36 / 100	66 ms	4936 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

// DFS sinh Euler tour từ đỉnh u
void dfs(int u, vector<bool>& vis, vvi& adj, vi& tour) {
    vis[u] = true;
    tour.push_back(u);
    for (int v : adj[u]) {
        if (!vis[v]) {
            dfs(v, vis, adj, tour);
            tour.push_back(u);
        }
    }
}

vvi create_map(int n, int m, vi a, vi b) {
    vvi adj(n + 1);
    for (int i = 0; i < m; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    vector<bool> vis(n + 1, false);
    vi tour;
    dfs(1, vis, adj, tour);
    const int K = 3 * n - 1;
    vector<set<pair<int, int>>> diags(2 * K - 1);
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            int diag_id = i + j;
            diags[diag_id].insert({i, j});
        }
    }
    vvi ans(K, vi(K));
    vvi diag_usage(n + 1);
    int current_diag = 0;
    for (int i = 0; i < (int)tour.size(); i++) {
        int color = tour[i];
        diag_usage[color].push_back(current_diag + 1);

        while (current_diag < 3 * (i + 1)) {
            for (auto [x, y] : diags[current_diag]) {
                ans[x][y] = color;
            }
            ++current_diag;
        }
    }
    for (int u = 1; u <= n; u++) {
        int idx = 0;
        for (int diag_id : diag_usage[u]) {
            for (auto [x, y] : diags[diag_id]) {
                if (idx >= (int)adj[u].size()) break;
                ans[x][y] = adj[u][idx++];
            }
        }
    }

    return ans;
}

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