Submission #1252743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252743		thelegendary08	World Map (IOI25_worldmap)	C++17	100 / 100	28 ms	3140 KiB

worldmap

#include "worldmap.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 45;
vvi adj(mxn), edj(mxn);
vi euler_tour;
struct DSU{
	int n; vi par, sz;
	DSU(int N){
		n = N; par.resize(n); sz.resize(n);
		f0r(i, n)par[i]=i,sz[i]=1; 
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int a, int b){
		a = find(a); b = find(b); 
		if(sz[a] < sz[b])swap(a,b);
		sz[a] += sz[b]; par[b] = a; 
	}
};

void dfs(int node, int from){ 
	euler_tour.pb(node);
	for(auto u : edj[node]){
		if(u != from)dfs(u, node), euler_tour.pb(node);
		
	}
}
std::vector<std::vector<signed>> create_map(signed N, signed M, std::vector<signed> A, std::vector<signed> B) {
	
  std::vector<std::vector<signed>> grid(2 * N, std::vector<signed>(2 * N, 1));
  f0r(i, N+1){
  	adj[i].clear(); edj[i].clear(); 
  }
  euler_tour.clear();
  vector<vpii>diags(4 * N - 1);
  vvi pending(N+1);
  f0r(i, 2 * N){
  	f0r(j, 2 * N){
  		diags[i + j].pb(mp(i,j));
  	}
  }
  f0r(i, M){
  	adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]);
  }
  DSU d = DSU(N+1);
  f0r(i, M){
  	int x = A[i]; int y = B[i];
  	if(d.find(x) != d.find(y)){
  		d.unite(x,y); edj[x].pb(y); edj[y].pb(x);
  	}
  }
  vector<vb>done(N+1, vb(N+1));
  vvi ans;
  vb vis(N+1);
  dfs(1,-1);
  int ptr = 0;
  f0r(i, N+1){
  	for(auto u : edj[i]){
  		done[i][u] = 1; done[u][i] = 1; 
  	}
  	// vout(edj[i]);
  }
  
  f0r(i, N+1){
  	sort(all(adj[i]));
  }
  vi diag_name(N+1);
  vi diag_length(N+1);
  for(auto v : euler_tour){
  	if(!vis[v]){
  		vi tmp; 
  		f0r(i, diags[ptr].size())tmp.pb(v); 
  		ans.pb(tmp);
  		ptr++;
  		vi t2; 
  		/*
  		for(auto x : pending[v]){
  			t2.pb(x);
  			done[v][x] = 1; done[x][v] = 1; 
  		}
  		if(v == 1){
  			// vout(t2);
  		}
  		for(auto u : adj[v]){
  			if(t2.size() >= diags[ptr].size())break;
  			if(!done[u][v]){
  				done[u][v] = 1; done[v][u] = 1; 
  				t2.pb(u);
  			}
  		}
  		if(v == 1){
  			// vout(t2);
  		}
  		for(auto u : adj[v]){
  			if(!done[u][v]){
  				pending[u].pb(v);
  			}
  		}
  		if(t2.empty())t2.pb(v);
  		*/
  		diag_name[v] = ptr;
  		diag_length[v] = diags[ptr].size();
  		ans.pb(t2);
  		ptr++;
  		vi t3;
  		f0r(i, diags[ptr].size())t3.pb(v); 
  		ans.pb(t3);
  		ptr++;
  		vis[v] = 1; 
  	}
  	else{
  		vi tmp; 
  		f0r(i, N)tmp.pb(v); 
  		ans.pb(tmp);
  		ptr++;
  	}
  }
   f0r(i, ans.size()){
  	// vout(ans[i]);
  }
  
  vpii ord; 
  FOR(i,1,N+1){
  	ord.pb(mp(diag_length[i], i));
  }
  sort(all(ord));
  f0r(i, ord.size()){
  	int v = ord[i].second;
  	int l = ord[i].first;
  	vi tmp;
  	vpii nxt;
  	for(auto u : adj[v]){
  		nxt.pb(mp(diag_length[u], u));
  	}
  	sort(all(nxt));
  	for(auto [d, u] : nxt){
  		if(tmp.size() == l)break;
  		if(!done[u][v]){
  			done[u][v] = 1; done[v][u] = 1;
  			tmp.pb(u);
  		}
  	}
  	if(tmp.size() == 0)tmp.pb(v);
  	ans[diag_name[v]] = tmp;
  }
  
  // vout(euler_tour);
  int p1 = 0; 
  // dout(ans.size());
  f0r(i, 4 * N - 1){
  	// if(diags[i].size() >= N){
  		if(p1 < ans.size()){
  			int p2 = 0;
	  		for(auto [x,y] : diags[i]){
	  			if(p2 == ans[p1].size()){
	  				grid[x][y] = ans[p1][p2-1];
	  			}
	  			else{
	  				grid[x][y] = ans[p1][p2];
	  				p2++;
	  			}
	  		}
	  		p1++;
  		}
  		
  	// }
  }
  
  f0r(i, ans.size()){
  	// vout(ans[i]);
  }
	
  return grid;
}

• 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