Submission #1249852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249852		Jakub_Wozniak	World Map (IOI25_worldmap)	C++20	86 / 100	44 ms	5704 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define st first
#define nd second
const int maxn = 109;
bool mat[maxn][maxn];
vector<vector<int>> ag;
int ng;
bool vis[maxn];
int aktr = 0;
int aktc = 0;

void DFS(int v)
{
  vis[v] = 1;
  for(int i = 0 ; i < 3*ng; i++)
  {
    ag[aktr][i] = v;
    int p = i/2+1;
    if(p > ng)continue;
    if(i%2 == aktc)
    {
      if(mat[v][p])ag[aktr][i] = p;
    }
  }
  aktr++;
  aktc ^= 1;

  for(int j = 1; j <= ng ; j++)
  {
    if(mat[v][j] && vis[j] == 0)
    {
      for(int i = 0; i < 3*ng ; i++)
      {
        if(i%2 == aktc)ag[aktr][i] = j;
        else ag[aktr][i] = v;
      }
      aktr++;
      DFS(j);
      aktc ^= 1;
      for(int i = 0; i < 3*ng ; i++)
      {
        if(i%2 == aktc)ag[aktr][i] = j;
        else ag[aktr][i] = v;
      }
      aktr++;
      aktc ^= 1;
    }
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) 
{
  ng = N;
  if(M == 0)
  {
    return {{1}};
  }
  vector<vector<int>> ans(3*N,vector<int>(3*N,0));
  ag = ans;
  for(int i =0 ; i < M ; i++)
  {
    mat[A[i]][B[i]] = 1;
    mat[B[i]][A[i]] = 1;
  }

  DFS(1);
  while(aktr < 3*ng)
  {
    for(int i = 0 ; i< 3*ng;i++)ag[aktr][i] = 1;
    aktr++;
  }
  
  for(int i = 1; i <= N ; i++)for(int j = 1; j <= N ; j++)mat[i][j] = 0;
  for(int i = 1; i <= N ; i++)vis[i] = 0;
  aktr = 0;
  return ag;
}

• 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