Submission #1281478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281478		M_W_13	World Map (IOI25_worldmap)	C++20	100 / 100	27 ms	4168 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 = 50;
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, c, it + 2 + e, 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) {
  rep(i, MAXN) {
    tr[i].clear();
    ile_pod[i] = 0;
    odw[i] = false;
    odw2[i] = false;
  }
  ans.clear();
  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;
      }
    }
  }
  set<pii> jakie;
  rep(i, m) {
    jakie.insert({A[i], B[i]});
    jakie.insert({B[i], A[i]});
  }
  rep(i, n) {
    jakie.insert({i + 1, i + 1});
  }
  // rep(i, 2 * n - 1) {
  //   rep(j, 2 * n) {
  //     if (jakie.find({ans[i][j], ans[i + 1][j]}) == jakie.end()) {
  //       rep(cos, 1) {
  //         cout << "ZLEEEEEEEEEEEEEEEEEEEEEEEE" << '\n';
  //       }
  //     }
  //   }
  // }
  // rep(i, 2 * n) {
  //   rep(j, 2 * n - 1) {
  //     if (jakie.find({ans[i][j], ans[i][j + 1]}) == jakie.end()) {
  //       rep(cos, 1) {
  //         cout << "ZLEEEEEEEEEEEEEEEEEEEEEEEE" << '\n';
  //       }
  //     }
  //   }
  // }
  // cout << "OK" << '\n';
  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