Submission #1252516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252516		dreamnguyen	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

#include "worldmap.h"
#include <vector>

using namespace std;

void paint(int d, int c, vector<vector<int>> &map) {
    for (int i = 0; i <= d; ++i)
        if (max(i, d - i) < (int)map.size())
            map[i][d - i] = c + 1;
}

void dfs(int u, int p, int n, int &t, vector<vector<int>> &map, const vector<vector<int>> &adj, vector<int> &vis) {
    vis[u] = 1;
    paint(t++, u, map);

    for (int v : adj[u])
        if (!vis[v])
            dfs(v, u, n, t, map, adj, vis);

    if (u == 0) return;

    int e = max(0, t - 2 * n + 1);
    paint(t++, u, map);
    paint(t++, u, map);
    paint(t++, p, map);

    for (int v : adj[u])
        if (vis[v] != 2)
            map[e++][t - 1 - e] = v + 1;

    vis[u] = 2;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    int K = 2 * N;
    vector<vector<int>> map(K, vector<int>(K, 1));
    vector<vector<int>> adj(N);
    vector<int> vis(N, 0);

    for (int i = 0; i < M; ++i) {
        int u = A[i] - 1, v = B[i] - 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int t = 0;
    dfs(0, 0, N, t, map, adj, vis);
    return map;
}

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