Submission #1251021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251021		David_M	World Map (IOI25_worldmap)	C++20	100 / 100	21 ms	2888 KiB

worldmap

#include "worldmap.h"

#include<bits/stdc++.h>

using namespace std;

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

void dfs(int x, int pa, int n, int &k, vector<vector<int>> &ans, auto &v, auto &f) {
    f[x] = 1;

    color(k, x, ans);
    k++;

    for (int y : v[x]) {
        if(!f[y])
            dfs(y, x, n, k, ans, v, f);
    }

    if(x == 0) return;

    int e = max(0, k - 2 * n + 1);

    color(k, x, ans);
    color(k+1, x, ans);
    color(k+2, pa, ans);

    for (int y : v[x])
        if(f[y] != 2)
            ans[e][k - e] = y + 1,
            e++;

    k += 3;

    f[x] = 2;
}


vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  vector<vector<int>> ans(2 * N, vector<int>(2 * N, 1)), v(N);
  vector<int> f(N, 0);

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

  int k = 0;
  dfs(0, 0, N, k, ans, v, f);

  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