| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1294580 | tschav_ | 세계 지도 (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
vector<vector<int>> adj;
adj.resize(n+1,vector<int>{});
for(int i = 0; i < m; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
if(m == 0){
return vector<vector<int>>{vector<int>{1}};
}
vector<int> row(n*n,0);
int C = 0 ;
for(int i = 1; i <= n; ++i){
vector<int> R;
vector<bool> vis(n+1,false);
auto dfs = [&](int ind, auto &&dfs) -> void {
vis[ind]=true;
++C;
R.push_back(ind);
for(auto &u : adj[ind]) {
if(vis[u] ) continue;
dfs(u,dfs);
if(C!=n)R.push_back(ind);
}
};
dfs(i, dfs);
if(R.size() < row.size()){
row = R;
}
}
for(int i = 0; i < row.size();++i){
cerr << row[i] << " ";
}
map<int,int>freq;
int sz = 1;
for(int i = 1; i < row.size();++i){
if(freq[row[i]]){
++sz;
}else{sz+=2;}
++freq[row[i]];
}
vector<vector<int>> ans(sz, vector<int>(sz, 1));
vector<bool> F(n+1,false); int last= 0;
int L = 0;
int lastt = 0;
int par = 1;
if(true){
queue<int> Q;
int u= row[L];
for(auto &v : adj[u]){
Q.push(v);
}
for(int i = 0; i < sz; ++i){
if((i & 1) == par or Q.empty()){
ans[i][0] = u;
}else{
ans[i][0] = Q.front();
Q.pop();
}
}
F[u]=true;
}
++L;
for(int i = 1; i < sz; ++i){
if(L == row.size()){
int V = row[L-1];
for(int j = 0; j < sz;++ j){
ans[j][i] = V;
}
continue;
}
int u = row[L];
// if(F[u]){
// lastt = i;
// for(int j = 0; j < sz;++ j){
// ans[j][i] = u;
// }
// ++L;
// continue;
// }
if(i==lastt+1){
int w = row[L-1];
//cerr << endl;
//cerr << u << " " << w << " " << L;
for(int j = 0; j < sz;++ j){
if((j & 1) == par){
ans[j][i] = u;
}else ans[j][i] = w;
}
par ^= 1;
if(F[u]){
par ^= 1;
++lastt;
++L;
}
continue;
}
if( i == lastt+2){
queue<int> Q;
for(auto &v : adj[u]){
Q.push(v);
}
for(int j = 0; j < sz; ++j){
if((j & 1) == par or Q.empty()){
ans[j][i] = u;
}else{
ans[j][i] = Q.front();
Q.pop();
}
}
F[u] = true;
lastt+=2;
++L;
}
}
return ans;
}
int main() {
int n = 5;
int m = 4;
vector<int> A = {1, 1, 2, 3};
vector<int> B = {2, 3, 4, 5};
auto ans = create_map(n,m,A,B);
for(auto &v: ans){
for(auto &i: v){
cout << i << " ";
}
cout << endl;
}
}