Submission #1256884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256884		ThylOne	World Map (IOI25_worldmap)	C++20	100 / 100	25 ms	2888 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
#include <cassert>
#include <utility>

using namespace std;
using grid = vector<vector<int>>;

vector<int> links[40];
vector<vector<int>> euleur_tour;
bool mem[40];
int K;
vector<int> diag_size;
void uniform_line(int i){
  euleur_tour.push_back(vector<int>(diag_size[euleur_tour.size()],i+1));
}
void add_damage(int i, vector<int> v){
  euleur_tour.push_back(vector<int>(diag_size[euleur_tour.size()],i+1));
  assert(v.size() <=euleur_tour.back().size());
  for(int j = 0 ; j < v.size() ; j++)
    euleur_tour[euleur_tour.size()-1][j] = v[j]+1;
}
int depth[40];
set<int> on_stack;
void dfs(int node,int papa=-1){
  on_stack.insert(node);
  uniform_line(node);
  mem[node] = true;
  vector<int> to_dam;
  for(int u:links[node]){
    if(mem[u]){
      if(on_stack.find(u)!=on_stack.end() && u!=papa){
        to_dam.push_back(u);
      }
    }else{
      depth[u] = depth[node] + 1;
      dfs(u, node);
      uniform_line(node);
    }  
  }
  on_stack.erase(node);
  if(node == 0)return; //base case
  add_damage(node, to_dam);
  uniform_line(node);
}
grid create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  diag_size.clear();
  for(int i = 0 ; i < N ; i++)links[i].clear();
  euleur_tour.clear();
  K  = 2*N-1;
  fill(mem, mem+40,false);
  fill(depth, depth+40,0);
  diag_size.shrink_to_fit();
  diag_size.resize(2*K-1,0);
  vector<pair<int,int>> dcoords[2*K-1];
  for(int x = 0 ; x < K ; x++){
    for(int y = 0 ; y < K ; y++){
      diag_size[x+y]+=1;
      dcoords[x+y].push_back(make_pair(x, y));
    }
  }
  grid ans(K, std::vector<int>(K, 1));
  
  for(int i = 0 ; i < M ; i++){
    A[i]--;
    B[i]--;
    links[A[i]].push_back(B[i]);
    links[B[i]].push_back(A[i]);
  }
  dfs(0);
  cerr << N << " " << euleur_tour.size() << " " << diag_size.size()<< endl;
  //assert(euleur_tour.size()==2*N-2);
  
  const auto lm = euleur_tour.back()[0];
  for(int i=euleur_tour.size();i<(int)diag_size.size();i++)
    uniform_line(lm);
  
  assert(euleur_tour.size() == diag_size.size());
  for(int i =0 ; i < euleur_tour.size() ;i++){
      assert(diag_size[i] == euleur_tour[i].size());

    for(int j=0;j<diag_size[i];j++){
      ans[dcoords[i][j].second][dcoords[i][j].first]=euleur_tour[i][j];
    }
  }
  //TODO penser a3 our les valeurs
  cerr  << "coucou " << endl;
  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