Submission #1252201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252201		inksamurai	World Map (IOI25_worldmap)	C++20	86 / 100	43 ms	5700 KiB

worldmap

#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define vec vector
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class H,class...T>
void print(const H&v,const T&...u){cout<<v<<' ',print(u...);}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
	int n=N;
	int m=M;

	vec<vi> graf(n);
	rep(i,m){
		A[i]--;
		B[i]--;
		graf[A[i]].pb(B[i]);
		graf[B[i]].pb(A[i]);
	}

	vi usd(n);
	vi par(n,-1);
	vi depth(n);
	auto dfs=[&](auto self,int v)->void{	
		usd[v]=1;

		for(auto u:graf[v]){
			if(usd[u]) continue;
	
			par[u]=v;
			depth[u]=depth[v]+1;
			self(self,u);
		}
	};
	dfs(dfs,0);

	rep(v,n){
		sort(all(graf[v]),[&](int l,int r){
			return depth[l]<depth[r];
		});
	}

	rng(i,1,n) assert(par[i]!=-1);

	const int n3=n*3;

	vec<vi> grid;
	int parity=0;
	int visited=0;

	usd=vi(n);

	auto needs_upload=[&](int v){
		bool fnd=0;
		for(auto u:graf[v]) if(!usd[u]){
			fnd=1;
		}
		return fnd;
	};

	auto rec=[&](auto self,int v)->void{
		usd[v]=1;
		visited+=1;

		{
			vi row;
			for(auto u:graf[v]){
				if(!parity){
					row.pb(v);
					row.pb(u);
				}else{
					row.pb(u);
					row.pb(v);
				}
			}
			while(sz(row)<n3) row.pb(v);
			
			grid.pb(row);
			parity^=1;
		}

		for(auto u:graf[v]){
			if(par[u]!=v) continue;
			if(needs_upload(u)){
				{
					// print("e",v,u);
					vi row;
					rep(i,n){
						if(!parity){
							row.pb(v);
							row.pb(u);
						}else{
							row.pb(u);
							row.pb(v);
						}
					}
					while(sz(row)<n3) row.pb(u);
					
					grid.pb(row);

					// parity^=1;
				}

				self(self,u);

				if(visited<n){
					vi row;
					rep(i,n){
						if(!parity){
							row.pb(u);
							row.pb(v);
						}else{
							row.pb(v);
							row.pb(u);
						}
					}
					while(sz(row)<n3) row.pb(v);
					
					grid.pb(row);

					// parity^=1;
				}
			}
		}
	};
	rec(rec,0);

	assert(sz(grid)<=n3);

	while(sz(grid)<n3){
		grid.pb(grid.back());
	}
	const int si=sz(grid);
	// print(sz(grid));
	rep(i,si){
		rep(j,si){
			grid[i][j]+=1;
		}
	}

	return grid;
}

// signed main(){
// 	vi a={1,1,1,2,2,3,3,3};
// 	vi b={2,3,4,3,4,4,5,6};
// 	map<pii,int> mp;
// 	rep(i,sz(a)){
// 		// print(a[i],b[i]);
// 		mp[minmax(a[i],b[i])]=1;
// 	}
// 	int n=6;
// 	int m=sz(a);
	
// 	auto grid=create_map(n,m,a,b);
// 	const int si=sz(grid);

// 	rep(i,si){
// 		// assert(sz(grid[i])==si);
// 		for(auto x:grid[i]) cout<<x<<" ";
// 		cout<<"\n";
// 	}

// 	auto check=[&](int i,int j,int i1,int j1){
// 		int x=grid[i][j];
// 		int y=grid[i1][j1];
// 		if(x==y){
// 			return;
// 		}
// 		// print(x,y);
// 		assert(mp.find(minmax(x,y))!=mp.end());
// 	};

// 	rep(i,si){
// 		rep(j,si){
// 			if(i+1<si){
// 				check(i,j,i+1,j);
// 			}
// 			if(j+1<si){
// 				check(i,j,i,j+1);
// 			}
// 		}
// 	}
// }

• 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