Submission #1309480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309480		Faisal_Saqib	World Map (IOI25_worldmap)	C++20	0 / 100	52 ms	7448 KiB

worldmap

#include <vector>
#include <iostream>
// #include "worldmap.h"
using namespace std;
const int N=50;
vector<int> ma[N],tour;
int h[N];
bool vis[N];
void dfs(int x,int p=0)
{
    vis[x]=1;
    tour.push_back(x); // O(n)
    for(auto y:ma[x])
    {
        if(y^p)
        {
            if(!vis[y])
            {
                h[y]=h[x]+1;
                dfs(y,x);
                tour.push_back(x); // O(m)
            }
        }
    }
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> edg0, std::vector<int> edg1)
{
    for(int i=0;i<=n;i++)
    {
        ma[i].clear();
        vis[i]=0;
    }
    for(int j=0;j<m;j++)
    {
        ma[edg0[j]].push_back(edg1[j]);
        ma[edg1[j]].push_back(edg0[j]);
    }
    tour.clear();
    dfs(1);
    int K=tour.size();
    int fK=K;
    vector<int> ftim(N+5,-1);
    vector<vector<int>> answer;
    for(int i=0;i<K;i++)
    {
        int x=tour[i];
        vector<int> row;
        for(int j=0;j<K;j++)
        {
            row.push_back(x);
        }
        answer.push_back(row); // O(2*n-1)
        if(ftim[x]!=-1)continue;
        ftim[x]=i;
        // O(n)
        // ma[x][j]
        int sz=ma[x].size();
        vector<int> cur;
        for(int j=0;j<sz;j++) // atmost n so 2*n
        {
            cur.push_back(ma[x][j]);
            cur.push_back(x);
        }
        fK=max(fK,(int)(cur.size()));
        answer.push_back(cur);
        answer.push_back(row);
    }
    fK=max(fK,(int)(answer.size()));
    for(auto&x:answer)
    {
        while(x.size()<fK)
        {
            x.push_back(x.back());
        }
    }
    while(answer.size()<fK)
    {
        answer.push_back(answer.back());
    }
    // if(fK>240)
    // {
    //     return {};
    // }
    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56