Submission #1254895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254895		PenguinsAreCute	World Map (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
	vector<vector<int>> adj(N);
	for(int i=0;i<M;i++) {
		adj[--A[i]].push_back(--B[i]);
		adj[B[i]].push_back(A[i]);
	}
	vector<vector<int>> ans(2*N,vector<int>(2*N,1));
	vector<int> diag(N);
	vector<int> cur(N);
	vector<bool> vis(N);
	auto filldiag = [N,&ans](int diag, int x) {
		for(int i=0;i<2*N;i++)
			if(diag-i>=0&&diag-i<2*N)
				ans[i][diag-i]=x;
	};
	auto dfs = [&adj,&vis,&diag,&filldiag,N,cnt=0](auto &dfs, int x) mutable -> void {
		vis[x] = 1;
		filldiag(cnt, x+1);
		filldiag(cnt+1, x+1);
		filldiag(cnt+2, x+1);
		diag[x] = cnt + 1;
		cnt += 3;
		for(auto i: adj[x])
			if(!vis[i]) {
				dfs(dfs, i);
				filldiag(cnt++, x+1);
			}
	};
	dfs(dfs, 0);
	for(int i=0;i<N;i++)
		cur[i] = max(0, diag[i] - (2 * N - 1));
	for(int i=0;i<M;i++) {
		if(abs(2 * N - 1 - diag[A[i]]) > abs(2 * N - 1 - diag[B[i]]))
			swap(A[i], B[i]);
		ans[cur[A[i]]][diag[A[i]]-cur[A[i]]] = B[i] + 1;
		cur[A[i]]++;
	}
	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