제출 #1258358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258358		allin27x	World Map (IOI25_worldmap)	C++20	100 / 100	106 ms	2888 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 44;
int k;
int n;
vector<vector<int>> mp;
int adj[N][N];
int vis[N];
int cur;
int diag[N];


void fill_current(int col){
	for (int i=0; i<k; i++)
		for (int j=0; j<k; j++)
			if (j-i == cur) mp[i][j] = col;
	cur++;
}

void fill_neighbors(int idx){
	vector<int> ng; for (int i=1; i<=n; i++) if (adj[idx][i]) ng.push_back(i);
	while (ng.size() < k) ng.push_back(idx);
	int nid = 0;
	for (int i=0; i<k; i++)
		for (int j=0; j<k; j++)
			if (j-i == diag[idx]) mp[i][j] = ng[nid++];
}

void dfs(int nw){
	vis[nw] = 1;
	fill_current(nw); 
	diag[nw] = cur++;
	fill_current(nw); 
	for (int c=0; c<=n; c++){
		if (!adj[c][nw] || vis[c]) continue;
		dfs(c); 
		fill_current(nw); 
	}
}

std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
	k = 2*n; ::n = n; 
	mp.assign(k, vector<int> (k,0));
	for (int i=0; i<N; i++) for (int j=0; j<N; j++) adj[i][j] = 0;
	for (int i=0; i<m; i++) adj[a[i]][b[i]] = 1, adj[b[i]][a[i]] = 1;
	for (int i=0; i<N; i++) vis[i] = 0;
	cur = -k+1;
	dfs(1);
	vector<pair<int,int>> nd;
	for (int i=1; i<=n; i++) nd.push_back({abs(diag[i]), i});
	sort(nd.begin(), nd.end());
	for (auto [_, idx]: nd){
		fill_neighbors(idx);
		for (int i=1; i<=n; i++) adj[i][idx] = 0, adj[idx][i] = 0;
	}
	return mp;
}

• 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