Submission #1251264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251264		arneves	세계 지도 (IOI25_worldmap)	C++20	100 / 100	23 ms	2888 KiB

worldmap

/*
           ______  _____  _______ _     _ _______ __   _  _____  _  _  _
          |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
          |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
 
 
                   .      .           .      .           .      .
                   _\/  \/_           _\/  \/_           _\/  \/_
                    _\/\/_             _\/\/_             _\/\/_
                _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_
                 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \
                    _/\/\_             _/\/\_             _/\/\_
                    /\  /\             /\  /\             /\  /\
                   '      '           '      '           '      '
 
*/
 
//#pragma GCC optimize("Ofast", "unroll-loops")
 
#include "bits/stdc++.h"
 
//#pragma GCC target("avx2")
//#pragma GCC target("lzcnt,popcnt")
 
using namespace std;
using ll = long long;
using bint = __int128;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define rep(i, a, b) for (int i=a; i<(b); ++i)
#define rev(i, a, b) for (int i=b-1; i>=(a); --i)
 
template <class Fun>
class y_combinator_result {
	Fun fun_;
 
  public:
	template <class T>
	explicit y_combinator_result(T&& fun)
		: fun_(std::forward<T>(fun)) {
	}
 
	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};
 
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
 
string yon(ll ans) {
	return ans ? "Yes" : "No";
}
 
template <typename T>
inline void ckmin(T& a, const T b) {
	if (a > b)
		a = b;
}
 
template <typename T>
inline void ckmax(T& a, const T b) {
	if (a < b)
		a = b;
}
 
inline double get_time() {
	return std::chrono::duration_cast<std::chrono::milliseconds>(
		   std::chrono::system_clock::now().time_since_epoch())
		   .count();
}
 
ll popcnt(ll x){return __builtin_popcountll(x);}
ll popcnt_sgn(ll x){return (__builtin_parityll(x)&1 ? -1:1);}
ll topbit(ll x){return (x==0 ? -1:63-__builtin_clzll(x));}
ll lowbit(ll x){return (x==0 ? -1:__builtin_ctzll(x));}
 
//----------------------------------------------------------------------

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){
	
	if(n==1){
		vector ans(1, vector<int>(1, 1));
		return ans;
	}
	
	vector adj(n, vector<int>());
	
	rep(i,0,m){
		adj[a[i]-1].pb(b[i]-1);
		adj[b[i]-1].pb(a[i]-1);
	}
	
	vector<int> order, vis(n, 0), pai(n, -1), depth(n), mxd(n, 0);
	
	auto dfs=y_combinator([&](auto self, int s) -> void{
		vis[s]=1;
		for(int u: adj[s]) if(vis[u]==0){
			pai[u]=s;
			depth[u]=depth[s]+1;
			mxd[u]=depth[u];
			self(u);
			ckmax(mxd[s], mxd[u]);
		}
	});
	
	depth[0]=0;
	dfs(0);
	
	auto dfs2=y_combinator([&](auto self, int s) -> void{
		order.pb(s);
		
		vector<pair<int,int>> e;
		for(int u: adj[s]) if(depth[u]==depth[s]+1) e.pb({mxd[u], u});
		
		sort(all(e));
		
		for(auto [_, u]: e){
			self(u);
			order.pb(s);
		}
	});
	
	dfs2(0);
	
	int k=2*n;
	
	vector<vector<int>> linhas;
	vis.assign(n, 0);
	
	for(int u: order){
		
		linhas.pb({u});
		
		if(vis[u]==0){
			vis[u]=1;
			
			vector<int> l;
			
			for(ll v: adj[u]) if(depth[v]<depth[u] && v!=pai[u]) l.pb(v);
			
			if(sz(l)==0) l.pb(u);
			linhas.pb(l);
			linhas.pb({u});
		}
	}
	
	assert(sz(linhas)==4*n-1);
	
	vector ans(k, vector<int>(k, -1));
	
	rep(i,0,4*n-1){
		
		int ss=min(i+1, 4*n-i-1);
		
		while(sz(linhas[i])<ss) linhas[i].pb(linhas[i].back());
		
		rep(y,0,2*n){
			int x=i-y;
			if(x<0 || x>2*n-1) continue;
			ans[x][y]=linhas[i].back();
			linhas[i].pop_back();
		}
	}
	
	rep(i,0,k) rep(j,0,k) ans[i][j]++;
	
	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