Submission #1281467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281467		M_W_13	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	580 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const int MAXN = 42;
vector<vector<int>> ans;
set<int> tr[MAXN];
bool odw[MAXN];
int ile_pod[MAXN];
bool odw2[MAXN];
int n, m;

void dfs2(int v) {
  ile_pod[v] = 0;
  odw2[v] = true;
  vector<int> us;
  set<int> wcz;
  for (auto syn: tr[v]) {
    if (odw2[syn]) {
      us.pb(syn);
    }
  }
  for (auto syn: tr[v]) {
    if (odw2[syn]) continue;    
    dfs2(syn);
    ile_pod[v] += ile_pod[syn] + 1;
  }
  for (auto x: us) {
    tr[v].erase(x);
  }
}

void dfs(int v, int c, int it, int l, int r) {
  // cout << "v = " << v << " l = " << l << " r = " << r << '\n';
  // cout << "XD" << endl;
  odw[v] = true;
  for (int y = l + c; y <= r; y += 2) {
    ans[it][y] = v;
  }
  int d = c ^ 1;
  for (int y = l + d; y <= r; y += 2) {
    if ((it - 1) >= 0) {
      ans[it - 1][y] = v;
    }
    if ((it + 1) < 2 * n) {
      ans[it + 1][y] = v;
    }
  }
  vector<int> syno;
  for (auto x: tr[v]) {
    syno.pb(x);
    // cout << "x = " << x << '\n';
  }
  int sz = syno.size();
  int iter = 0;
  for (int y = l + d; y <= r; y += 2) {
    if (iter < sz) {
      ans[it][y] = syno[iter];
    }
    else {
      ans[it][y] = v;
    }
    iter++;
  }
  vector<pii> vec;
  int l2 = l;
  for (auto syn: tr[v]) {
    if (odw[syn]) continue;
    for (int x = it + 1; x < 2 * n; x++) {
      ans[x][l2] = v;
    }
    l2++;
    int e = c;
    if (ans[it][l2] == v) {
      e ^= 1;
    }
    // cout << "v = " << v << " pod = " << ile_pod[v] << '\n';
    dfs(syn, e, it + 2, l2, l2 + 2 * ile_pod[syn]);
    l2 = l2 + 2 * ile_pod[syn] + 1;
  }
  for (int x = it + 1; x < 2 * n; x++) {
    ans[x][l2] = v;
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  n = N;
  m = M;
  rep(i, 2 * n) {
    ans.pb({});
    rep(j, 2 * n) {
      ans[i].pb(-1);
    }
  }
  rep(i, m) {
    int a = A[i];
    int b = B[i];
    tr[a].insert(b);
    tr[b].insert(a);
  }
  // cout << "FR" << endl;
  dfs2(1);
  dfs(1, 0, 0, 0, 2 * n - 2);
  rep(i, 2 * n) {
    rep(j, 2 * n) {
      if (ans[i][j] == -1) {
        int kt = -1;
        if (i > 0 && ans[i - 1][j] >= 0) {
          kt = ans[i - 1][j];
        }
        else if (j > 0) {
          kt = ans[i][j - 1];  
        }
        ans[i][j] = kt;
      }
    }
  }
  return ans;
}

• 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