Submission #1264949

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

worldmap

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

void dfs(int x, vector<vector<int>> &AR, vector<int> &pos, vector<vector<int>> &adj, vector<int> &order, int &buff)
{
  pos[x] = buff++;
  order.push_back(x);
  for (int i=0; i<AR[x].size(); i++)
  {
    if (pos[AR[x][i]]!=-1)
    {
      adj[AR[x][i]][x] = 1;
      continue;
    }
    dfs(AR[x][i], AR, pos, adj, order, buff);
    order.push_back(x);
  }
}

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

  vector<vector<int>> ans(2 * N, vector<int>(2 * N, 1));
  vector<vector<int>> AR(N), adj(N, vector<int>(N,0));
  vector<int> order, pos(N, -1);
  for (int i=0; i<M; i++)
  {
    AR[A[i]-1].push_back(B[i]-1);
    AR[B[i]-1].push_back(A[i]-1);
  }
  int buff=0;
  dfs(0, AR, pos, adj, order, buff);
  vector<int> S;
  for (int i=0; i<order.size(); i++)
  {
    if (S.size()<2 || S[S.size()-2]!=order[i])
      S.push_back(order[i]);
    else
      S.pop_back();
    for (int j=0; j<2*N; j++)ans[i][j] = S.back()+1;
    for (int j=0; j<S.size(); j++)
    {
      ans[i][2*j] = S[j]+1;
      ans[i][2*j+1] = S[j]+1;
    }
    for (int j=0; j<S.size(); j++)
    {
      if (adj[S[j]][S.back()])
      {
        ans[i][2*j+1]=S.back()+1;
        ans[i][2*j+2]=S[j]+1;
      }
    }
  }
  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