Submission #1307831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307831		exoworldgd	World Map (IOI25_worldmap)	C++20	86 / 100	43 ms	5596 KiB

worldmap

#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<vector<int>>g(n),ans(3*n,vector<int>(3*n)),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]={},used[n]={},cur=n;
    vector<int>depth(n),tour,ra,rb;
    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;i<m-n+1;i++)h[ra[i]].push_back(rb[i]);
    for(int i=0;i<2*n-1;i++){
        if(!used[tour[i]]){
            int pos=0;
            for(int j=0;j<3*n;j++){
                int ya=cur-j,yb=cur+1-j,yc=cur+2-j;
                if(ya>=0&&ya<3*n)ans[j][ya]=tour[i];
                if(yb>=0&&yb<3*n)pos<(int)h[tour[i]].size()?(ans[j][yb]=h[tour[i]][pos],pos++):ans[j][yb]=tour[i];
                if(yc>=0&&yc<3*n)ans[j][yc]=tour[i];
            }
            used[tour[i]]=1,cur+=3;
        }else{
            for(int j=0,ya;j<3*n;j++)ya=cur-j,ya>=0&&ya<3*n?ans[j][ya]=tour[i]:0;
            cur++;
        }
    }
    for(int i=0;i<(int)ans.size();i++)for(int j=0;j<(int)ans.size();j++)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: 42 / 56