제출 #1256752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256752		medmdg	World Map (IOI25_worldmap)	C++20	0 / 100	5 ms	836 KiB

worldmap

#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
vector<vector<ll>> Graph,Tree;
map<ll,bool> vis;
void dfsTree(ll ind,ll par=-1){
  if(par==-1)
  {
    vis.clear();
    vis[ind]=true;
  }
  for(auto x:Graph[ind]){
    if(vis[x])continue;
    Tree[ind].push_back(x);
    vis[x]=true;
    dfsTree(x,ind);
  }
}
map<ll,ll> keyInd;
vector<ll> line(ll ind,ll offset=0){
  keyInd[ind]=offset;
  vector<ll> ans(1,ind);
  for(int i=0;i<Tree[ind].size();i++){
    ans.push_back(ind);
    ans.push_back(Tree[ind][i]);
    vector<ll> temp=line(Tree[ind][i],offset+ans.size());
    for(auto x:temp)ans.push_back(x);
    ans.push_back(Tree[ind][i]); 
  }
  return ans;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  n=N,m=M;
  Graph.clear();
  Tree.clear();
  Graph.resize(n);
  Tree.resize(n);
  for(int i=0;i<m;i++){
    Graph[A[i]-1].push_back(B[i]-1);
    Graph[B[i]-1].push_back(A[i]-1);
  }
  dfsTree(0);
  
  vector<ll> ans=line(0);
  vector<vector<int>> t(ans.size(),vector<int>(ans.size()));
  for(int i=0;i<ans.size();i++){
    for(int j=0;j<ans.size();j++){
      t[i][j]=ans[j]+1;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<Graph[i].size();j++){
      t[keyInd[i]][2*j]=Graph[i][j]+1;
    }
  }
  return t;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56