Submission #1253422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253422		dreamnguyen	World Map (IOI25_worldmap)	C++20	36 / 100	63 ms	4932 KiB

worldmap

/*
 .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.   .----------------.  .-----------------. .----------------.   .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .-----------------. .----------------.  .----------------.  .----------------.  .----------------.  .-----------------.
| .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. |
| | ____   ____  | || | _____  _____ | || | ____   ____  | || |     _____    | || |  _________   | || |  _________   | | | |      __      | || | ____  _____  | || |  ________    | | | |  _________   | || |  _______     | || |     _____    | || |  _________   | || |  _________   | || | ____  _____  | || |    ______    | || | _____  _____ | || |  _________   | || |  ____  ____  | || | ____  _____  | |
| ||_  _| |_  _| | || ||_   _||_   _|| || ||_  _| |_  _| | || |    |_   _|   | || | |_   ___  |  | || | |  _   _  |  | | | |     /  \     | || ||_   \|_   _| | || | |_   ___ `.  | | | | |  _   _  |  | || | |_   __ \    | || |    |_   _|   | || | |_   ___  |  | || | |  _   _  |  | || ||_   \|_   _| | || |  .' ___  |   | || ||_   _||_   _|| || | |_   ___  |  | || | |_  _||_  _| | || ||_   \|_   _| | |
| |  \ \   / /   | || |  | |    | |  | || |  \ \   / /   | || |      | |     | || |   | |_  \_|  | || | |_/ | | \_|  | | | |    / /\ \    | || |  |   \ | |   | || |   | |   `. \ | | | | |_/ | | \_|  | || |   | |__) |   | || |      | |     | || |   | |_  \_|  | || | |_/ | | \_|  | || |  |   \ | |   | || | / .'   \_|   | || |  | |    | |  | || |   | |_  \_|  | || |   \ \  / /   | || |  |   \ | |   | |
| |   \ \ / /    | || |  | '    ' |  | || |   \ \ / /    | || |      | |     | || |   |  _|  _   | || |     | |      | | | |   / ____ \   | || |  | |\ \| |   | || |   | |    | | | | | |     | |      | || |   |  __ /    | || |      | |     | || |   |  _|  _   | || |     | |      | || |  | |\ \| |   | || | | |    ____  | || |  | '    ' |  | || |   |  _|  _   | || |    \ \/ /    | || |  | |\ \| |   | |
| |    \ ' /     | || |   \ `--' /   | || |    \ ' /     | || |     _| |_    | || |  _| |___/ |  | || |    _| |_     | | | | _/ /    \ \_ | || | _| |_\   |_  | || |  _| |___.' / | | | |    _| |_     | || |  _| |  \ \_  | || |     _| |_    | || |  _| |___/ |  | || |    _| |_     | || | _| |_\   |_  | || | \ `.___]  _| | || |   \ `--' /   | || |  _| |___/ |  | || |    _|  |_    | || | _| |_\   |_  | |
| |     \_/      | || |    `.__.'    | || |     \_/      | || |    |_____|   | || | |_________|  | || |   |_____|    | | | ||____|  |____|| || ||_____|\____| | || | |________.'  | | | |   |_____|    | || | |____| |___| | || |    |_____|   | || | |_________|  | || |   |_____|    | || ||_____|\____| | || |  `._____.'   | || |    `.__.'    | || | |_________|  | || |   |______|   | || ||_____|\____| | |
| |              | || |              | || |              | || |              | || |              | || |              | | | |              | || |              | || |              | | | |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'   '----------------'  '----------------'  '----------------'   '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------' 
*/
#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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