Submission #1255368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255368		inksamurai	World Map (IOI25_worldmap)	C++20	100 / 100	35 ms	2888 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]--;
		// print(A[i],B[i]);
		graf[A[i]].pb(B[i]);
		graf[B[i]].pb(A[i]);
	}

	vi usd(n),par(n,-1),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);

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

	const int n2=n*2;

	vec<vi> grid;
	vec<vi> f(n);
	usd=vi(n);

	auto has_back_edge=[&](int u,int v){
		return find(all(graf[u]),v)!=graf[u].end() and par[v]!=u;
	};

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

		vi row;
		if(v){
			int up=par[v];
			while(1){
				row.pb(up);
				row.pb(up);
				if(!up) break;
				up=par[up];
			}

			while(sz(row)<n2) row.insert(row.begin(),v);

			int c=count(all(row),v);

			for(int j=c;j<n2;j++){
				if(has_back_edge(row[j],v)){
					row[j+1]=v;
					if(j+2<n2 and !has_back_edge(row[j+2],v)){
						row[j+2]=row[j];
						j+=3;
					}else{
						j++;
					}
				}
			}
			// print();
		}else{
			row=vi(n2,0);
		}
		f[v]=row;
		grid.pb(row);

		for(auto u:graf[v]){
			if(par[u]!=v) continue;

			self(self,u);

			grid.pb(row);
		}
	};
	rec(rec,0);

	// if(sz(grid)>n2){
	// 	cout<<"what\n";
	// 	return grid;
	// }

	assert(sz(grid)<=n2);

	while(sz(grid)<n2) 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,4,5,4,6,7,7,6,8,8};
// 	vi b={2,3,4,5,6,6,7,5,4,8,1,5};
// 	map<pii,int> mp;
// 	rep(i,sz(a)){
// 		// print(a[i],b[i]);
// 		mp[minmax(a[i],b[i])]=1;
// 	}
// 	int n=max(*max_element(all(a)),*max_element(all(b)));
// 	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: 56 / 56