Submission #1254258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254258		KLPP	World Map (IOI25_worldmap)	C++20	86 / 100	53 ms	29532 KiB

worldmap

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

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;

int c;
int n;

vector<int> nei[1'000'000];
bool vis[1'000'000];
int table[1000][1000];
bool parity;
int row;

void transition(int X, int Y){
  // cout<<"T "<<X<<" "<<Y<<endl;
  rep(i,0,c){
    if((parity^(i&1))){
      table[row][i]=X;
    }else{
      table[row][i]=Y;
    }
  }
  row+=1;
  // parity^=1;
}

void DFS(int node){
  if(!vis[node]){
    // cout<<"N "<<node<<endl;
    int C=0;
    rep(i,0,c){
      if((parity^(i&1))){
        table[row][i]=nei[node][C%nei[node].size()];
        C+=1;
      }else{
        table[row][i]=node;
      }
    }
    row+=1;
    parity^=1;
  }
  vis[node]=true;
  trav(a,nei[node]){
    if(!vis[a]){
      transition(a,node);
      DFS(a);
      transition(node,a);
    }
  }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
  n=N;
  c=3*n;
  rep(i,0,c){
    rep(j,0,c){
      table[i][j]=0;
    }
  }
  rep(i,0,M)A[i]--,B[i]--;
  rep(i,0,n)nei[i].clear();
  rep(i,0,M){
    nei[A[i]].push_back(B[i]);
    nei[B[i]].push_back(A[i]);
  }
  
  rep(i,0,n)vis[i]=false;
  parity=false;
  row=0;
  if(N>1)DFS(0);
  
  vector<vector<int> > ans(c);
  rep(i,0,c){
    ans[i].resize(c);
    rep(j,0,c){
      ans[i][j]=table[i][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: 42 / 56