Submission #1255185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255185		yuichiro17	World Map (IOI25_worldmap)	C++20	100 / 100	24 ms	2888 KiB

worldmap

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

bool visited[40];
vector<int>et;
vector<vector<int>>adj;
void dfs(int x){
  et.push_back(x);
  for(int i:adj[x]){
    if(visited[i])continue;
    visited[i]=true;
    dfs(i);
    et.push_back(x);
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  if(N==1)return {{1}};
  vector<vector<int>>ans(2*N,vector<int>(2*N,1));
  for(int i=0;i<N;i++)visited[i]=false;
  et.clear();
  adj.resize(N);
  for(int i=0;i<N;i++)adj[i].clear();
  vector<vector<bool>>adjm(N,vector<bool>(N,false));
  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);
    adjm[A[i]-1][B[i]-1]=true;
    adjm[B[i]-1][A[i]-1]=true;
  }
  visited[0]=true;
  dfs(0);
  vector<vector<pair<int,int>>>diag(4*N);
  for(int i=0;i<2*N;i++){
    for(int j=0;j<2*N;j++){
      diag[i+j].push_back({i,j});
    }
  }
  for(int i=0;i<N;i++)visited[i]=false;
  for(int i=0;i<2*N-2;i++){
    adjm[et[i]][et[i+1]]=false;
    adjm[et[i+1]][et[i]]=false;
  }
  int i=1;
  vector<array<int,3>>d;
  for(int j=1;j<2*N-1;j++){
    while(!diag[i].empty()){
      ans[diag[i].back().first][diag[i].back().second]=et[j]+1;
      diag[i].pop_back();
    }
    i++;
    if(visited[et[j]])continue;
    visited[et[j]]=true;
    d.push_back({min(i,4*N-1-i),i,et[j]});
    i++;
    while(!diag[i].empty()){
      ans[diag[i].back().first][diag[i].back().second]=et[j]+1;
      diag[i].pop_back();
    }
    i++;
  }
  sort(d.begin(),d.end());
  for(int i=0;i<N;i++){
    for(int j=0;j<i;j++){
      if(adjm[d[i][2]][d[j][2]]){
        ans[diag[d[i][1]].back().first][diag[d[i][1]].back().second]=d[j][2]+1;
        diag[d[i][1]].pop_back();
      }
    }
    while(!diag[d[i][1]].empty()){
      ans[diag[d[i][1]].back().first][diag[d[i][1]].back().second]=d[i][2]+1;
      diag[d[i][1]].pop_back();
    }
  }
  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