Submission #1251790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251790		PoonYaPat	World Map (IOI25_worldmap)	C++20	100 / 100	28 ms	2884 KiB

worldmap

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

int n,m,avai[45],cnt,pos[45];
vector<int> adj[45],ord;
bool vis[45];

void dfs(int x) {
  vis[x]=true;
  if (cnt!=n) ord.push_back(x);
  ++cnt;

  for (auto s : adj[x]) {
    if (vis[s]) continue;
    dfs(s);
    if (cnt!=n) ord.push_back(x);
  }
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  n=N; m=M; cnt=0;
  memset(avai,-1,sizeof(avai));
  for (int i=1; i<=n; ++i) adj[i].clear();
  ord.clear();
  memset(vis,0,sizeof(vis));

  vector<vector<int>> ans(2*n, vector<int>(2*n));
  for (int i=0; i<2*n; ++i) for (int j=0; j<2*n; ++j) ans[i][j]=0;
  
  for (int i=0; i<m; ++i) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  dfs(1);

  int idx=0;
  for (int i=0; i<(int)(ord.size()); ++i) {
    int city=ord[i];
    for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ans[j][idx-j]=city;
    ++idx;

    if (avai[city]==-1) {
      avai[city]=0;
      for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ++avai[city];
      pos[city]=idx;
      ++idx;

      for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ans[j][idx-j]=city;
      ++idx;
    }
  }
  for (int i=idx; i<4*n-1; ++i) for (int j=0; j<=i; ++j) if (j<2*n && i-j<2*n) ans[j][i-j]=ord.back();

  vector<int> v;
  for (int i=1; i<=n; ++i) v.push_back(i);
  sort(v.begin(), v.end(), [](int a, int b){
    return avai[a]<avai[b];
  });
  int rnk[n+5];
  for (int i=0; i<n; ++i) rnk[v[i]]=i;

  for (int i=1; i<=n; ++i) {
    vector<int> temp;
    for (auto s : adj[i]) if (rnk[s]<rnk[i]) temp.push_back(s);
    int idx=0;
    for (int j=0; j<=pos[i]; ++j) {
      if (j<2*n && pos[i]-j<2*n) {
        if (idx==temp.size()) ans[j][pos[i]-j]=i;
        else ans[j][pos[i]-j]=temp[idx++];
      }
    }
  }
  
  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