Submission #1250551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250551		nikd	World Map (IOI25_worldmap)	C++20	86 / 100	44 ms	5448 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {

  std::vector<std::vector<int>> ans(3 * N, std::vector<int>(3 * N, 1));
  vector<vector<bool>> changed(3*N, vector<bool>(3*N, 0));
  
  vector<vector<int>> adj(N);
  for(int i = 0; i<M; i++){
    adj[A[i]-1].push_back(B[i]-1);
    adj[B[i]-1].push_back(A[i]-1);
  }
  
  vector<bool> vis(N, 0);
  vector<vector<int>> back(N);
  vector<vector<int>> t(N);

  auto dfs = [&](auto&& dfs, int v, int p)->void{
    vis[v] = 1;
    for(int u: adj[v]){
      if(u == p) continue;
      if(vis[u]) back[u].push_back(v);
      else{
        t[v].push_back(u);
        dfs(dfs, u, v);
      }
    }
    return;
  };

  dfs(dfs, 0, -1);
  vector<int> proc(N, INT_MAX);
  int timer = 0;
  auto rec = [&](auto&& rec, int c, int i0, int j0)->int{
    proc[c] = timer++;
    for(int i = i0+3; i<3*N; i++) ans[i][j0] = c+1;
    int curr_j = j0+1;
    for(int u: t[c]){
      curr_j = rec(rec, u, i0+3, curr_j)+1;
      for(int i = i0+3; i<3*N; i++) ans[i][curr_j] = c+1;
      curr_j++;
    } 
    curr_j--;
    int curr_j2 = j0+1;
    for(int u: back[c]){
      if(proc[u] < proc[c]) continue;
      ans[i0+1][curr_j2] = u+1;
      changed[i0+1][curr_j2] = 1;
      curr_j2+=2;
    }
    curr_j2--;
    for(int i = i0; i<i0+3; i++){
      for(int j = j0; j<=max(curr_j, curr_j2); j++) if(!changed[i][j]) ans[i][j] =c+1;
    }
    for(int j = curr_j+1; j<=curr_j2; j++){
      for(int i = i0+3; i<3*N; i++){
        ans[i][j] = c+1;
      }
    }
    //assert(curr_j2 < curr_j-1);
    return max(curr_j, curr_j2);
  };
  rec(rec, 0, 0, 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: 42 / 56