Submission #1255660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255660		TadijaSebez	World Map (IOI25_worldmap)	C++20	100 / 100	21 ms	2884 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
    vector<vector<int>> E(n+1);
    vector<int> ord;
    vector<bool> was(n+1,false);
    for(int i=0;i<m;i++){
        E[A[i]].pb(B[i]);
        E[B[i]].pb(A[i]);
    }
    vector<int> dep(n+1,0);
    vector<vector<int>> ans(2*n,vector<int>(2*n));
    vector<int> sz(n+1,0);

    function<int(int,int,int)> DFS=[&](int x,int d,int offs){
        was[x]=true;
        dep[x]=d;
        sz[x]=1;
        int L=offs;
        int R=L;
        for(int i=d*2;i<2*n;i++){
            ans[i][L]=x;
        }
        vector<int> dw;
        for(int y:E[x]){
            if(!was[y]){
                R+=DFS(y,d+1,R+1);
                R++;
                sz[x]+=sz[y];
                for(int i=d*2;i<2*n;i++){
                    ans[i][R]=x;
                }
            }else if(dep[y]>dep[x]){
                dw.pb(y);
            }
        }
        int top=d*2;
        for(int j=L+1;j<R;j++){
            if(j%2!=d%2 && dw.size()){
                ans[top][j]=dw.back();
                dw.pop_back();
                if(top>0){
                    ans[top-1][j]=x;
                }
            }else{
                ans[top][j]=x;
            }
            if(!ans[top+1][j]){
                ans[top+1][j]=x;
            }
        }
        return R-L+1;
    };
    DFS(1,0,0);
    for(int i=0;i<2*n;i++){
        ans[i][2*n-1]=1;
    }
    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