Submission #1257387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257387		Muhammad_Aneeq	World Map (IOI25_worldmap)	C++20	86 / 100	48 ms	5188 KiB

worldmap

#include "worldmap.h"
#include "bits/stdc++.h"
using namespace std;
int const MN=45;
vector<int>nei[MN]={};
set<int>rel[MN]={};
int par[MN]={};
int h[MN]={};
int pr[MN]={};
int root(int n)
{
    return (par[n]==n?n:par[n]=root(par[n]));
}
bool merge(int u,int v)
{
    u=root(u);
    v=root(v);
    if (u==v)
        return 0;
    par[v]=u;
    return 1;
}
vector<int>cur;
bool w;
void dfs(int u,int p=-1)
{
    if (w)
        cur.push_back(u);
    pr[u]=p;
    for (auto i:nei[u])
    {
        if (i==p) continue;
        h[i]=h[u]+1;
        dfs(i,u);
        cur.push_back(u);
    }
    if (nei[u].size()==1&&u!=1)
        w=1;
    cur.push_back(-u);
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) 
{
    if (N==1)
    {
        return {{1}};
    }
    w=0;
    cur={};
    for (int i=1;i<=N;i++)
    {
        nei[i]={};
        rel[i]={};
        par[i]=i;
    }
    for (int i=0;i<M;i++)
    {
        rel[A[i]].insert(B[i]);
        rel[B[i]].insert(A[i]);
        if (merge(A[i],B[i]))
        {
            nei[A[i]].push_back(B[i]);
            nei[B[i]].push_back(A[i]);
        }
    }
    h[1]=0;
    dfs(1);
    int sz=cur.size();
    pr[1]=1;
    // for (auto i:cur)
    //     cout<<i<<' ';
    // cout<<endl;
    vector<vector<int>>ans;
    for (int j=0;j<sz;j++)
    {
        vector<int>z;
        int i=cur[j];
        if (i<0)
        {
            bool w=0;
            if (ans.size())
            {
                int pr=abs(cur[j-1]);
                if (ans.back()[0]==pr)
                    w=0;
                else
                    w=1;   
                if (pr==-i)
                    w=1-w;
            }
            for (auto j:rel[-i])
            {
                if (w)
                {
                    z.push_back(j);
                    z.push_back(-i);
                }
                else
                {
                    z.push_back(-i);
                    z.push_back(j);
                }
            }
            while (z.size()<sz)
                z.push_back((z.size()%2==w)?-i:pr[-i]);
        }
        else
        {
            bool w=0;
            int pr=abs(cur[j-1]);
            if (ans.size())
            {
                if (ans.back()[0]==pr)
                    w=0;
                else
                    w=1;   
            }
            for (int j=0;j<sz;j++)
            {
                z.push_back((j%2==w?i:pr));
            }
        }
        ans.push_back(z);
    }
    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