Submission #1250948

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

worldmap

#include "worldmap.h"

#include<bits/stdc++.h>

using namespace std;

vector<int> v[50];
int n, k;
int f[50];

void dfs(int x, int pa, vector<vector<int>> &ans) {
//    cout << "[x]: " << x << endl;
    f[x] = 1;

    for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
        ans[i][k - i] = x;
    }
    k++;

    for (int y : v[x]) {
        if(f[y]) continue;
        dfs(y, x, ans);
//        cout << x << "AAA" << endl;
    }

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

    if(x != 0) {
        for (int y : v[x]) {
            if(f[y] == 2) continue;
            assert(f[y] == 1);
            ans[e][k - e] = y;
            e++;
        }
        while (e <= min(k, 2 * n - 1)) {
            ans[e][k - e] = x;
            e++;
        }
        k++;


        for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
            ans[i][k - i] = x;
        }

        k++;

        for (int i = max(0, k - 2 * n + 1); i <= min(k, 2 * n - 1); ++i) {
            ans[i][k - i] = pa;
        }
        k++;
        f[x] = 2;
    }

//    cout << "[x]: " << x << endl;


}


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, 0));
  n = N;

  for (int i = 0; i < 50; ++i) {
    v[i].clear();
    f[i] = 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);
  }


  dfs(0, 0, ans);

//  assert(k == 4 * N - 2);


  for (int i = 0; i < 2 * N; ++i) {
    for (int j = 0; j < 2 * N; ++j) {
        ans[i][j]++;
//        cout << ans[i][j] << " ";
    }
//    cout << endl;
  }

  k = 0;
  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