| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1307833 | exoworldgd | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math,omit-frame-pointer")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include "worldmap.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<vector<int>>create_map(int n,int m,vector<int>a,vector<int>b){
vector<int>g[n],tour,ra,rb,depth(n),rank(n,-1),holder(n,-1),h[n];
for(int i=0;i<m;i++)a[i]--,b[i]--,g[a[i]].push_back(b[i]),g[b[i]].push_back(a[i]);
int vis[n]={},cur=0,parity=0;
function<void(int)>dfs=[&](int x){
vis[x]=1,tour.push_back(x);
for(int i:g[x]){
if(!vis[i])depth[i]=depth[x]+1,dfs(i),tour.push_back(x);
else if(depth[x]<depth[i])ra.push_back(x),rb.push_back(i);
}
};
dfs(0);
for(int i=0,d;i<2*n-1;i++)d=min(i,2*n-2-i),rank[tour[i]]<d?rank[tour[i]]=d,holder[tour[i]]=i:0;
for(int i=0;i<m-(n-1);i++){
if(rank[ra[i]]<rank[rb[i]])swap(ra[i],rb[i]);
h[ra[i]].push_back(rb[i]);
}
vector<vector<int>>ans(240,vector<int>(240));
for(int i=0;i<2*n-1;i++){
if(i==holder[tour[i]]){
int pos=0;
for(int j=0;j<2*n;j++){
int ya=cur-j,yb=cur+1-j,yc=cur+2-j;
if(ya>=0&&ya<2*n)ans[j][ya]=tour[i];
if(yb>=0&&yb<2*n)pos<int(h[tour[i]].size())?(ans[j][yb]=h[tour[i]][pos],pos++):ans[j][yb]=tour[i];
if(yc>=0&&yc<2*n)ans[j][yc]=tour[i];
}
cur+=3,parity^=1;
}else{
for(int j=0,ya;j<2*n;j++)ya=cur-j,ya>=0&&ya<2*n?ans[j][ya]=tour[i]:0;
cur++;
}
}
for(int i=0;i<ans.size();i++)for(int j=0;j<ans.size();j++)if(!(i<2*n&&j<2*n))ans[i][j]=(i<2*n?ans[i][j-1]:ans[i-1][j]);
for(int i=0;i<ans.size();i++)for(int j=0;j<ans.size();j++)ans[i][j]++;
return ans;
}
