Submission #1256203

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

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<int> euler;
v<bool> vis;
v<v<int>> adj;
v<int> par;
v<int> h;

void dfs(int n, int p=-1, int d=0) {
  //cout << "DFS: " << n << endl;
  vis[n] = true;
  par[n] = p;
  h[n] = d;
  euler.push_back(n);
  for (auto x : adj[n]) {
    if (!vis[x]) {
      dfs(x, n, d+1);
      euler.push_back(n);
    }
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  //cout << euler.size() << endl; for (auto x : euler) cout << x << " "; cout << endl;
  if (M == 0) {
    return {{1}};
  }
  adj.resize(N);
  vis.assign(N, false);
  v<v<int>> grid(N, v<int>(N, 0));
  par.assign(N, -1);
  h.assign(N, 0);
  rep(i, 0, M) {
    int a = A[i];
    int b = B[i];
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
    grid[a][b] = 1;
    grid[b][a] = 1;
  }
  dfs(0);
  int n = 2*N;
  v<v<int>> f(N, v<int>(n));
  rep(i, 0, N) {
    f[i] = v<int>(n, i+1);
    int padre = par[i];
    if (padre == -1) continue;
    for (int j = n-h[i]*2; j < n-1; j += 2) {
      if (padre == -1) continue;
      f[i][j] = padre+1;
      f[i][j+1] = padre+1;
      padre = par[padre];
    }
  }

  rep(i, 0, N) {
    for (int j=0;j<n-1; j+=2) {
      int a = f[i][j]-1;
      if (a == par[i]) continue;
      if (par[a] == -1) {
        if (grid[i][a]) {
          f[i][j+1] = i+1;
        }
      }
      else {
        if (grid[i][a]) {
          if (grid[i][par[a]]) {
            f[i][j+1] = i+1;
          }
          else {
            f[i][j+1] = i+1;
            f[i][j+2] = a+1;
            j += 2;
          }
        }
      }
    }
  }

  //cout << "hola?" << endl;
  v<v<int>> ans(2*N, v<int>(2*N, 1));
  //cout << euler.size() << " " << 2*N << endl;
  rep(i, 0, (int)euler.size()) {
    ans[i] = f[euler[i]];
  }
  euler.clear();
  adj.clear();
  grid.clear();
  h.clear();
  par.clear();
  vis.clear();
  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