Submission #1252867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252867		abcdxyz123	World Map (IOI25_worldmap)	C++17	100 / 100	22 ms	2888 KiB

worldmap

#include "worldmap"
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
using namespace std;
#define maxn 45
int n;
vector<int>adj[maxn];
int color[maxn];
int cur;
vector<vector<int>>res;
int depth[maxn];
void Fill(int k,vector<int>vec)
{
    int cnt=0;
    for(int i=0;i<=k;i++)
    {
        int x=i;
        int y=k-i;
        if(x>=2*n||y>=2*n)continue;
        res[x][y]=vec.back();
        if(vec.size()>=2)vec.pop_back();
        else cnt=1;
    }
    if(cnt==0)
    {
        //assert(0);
        cout<<k<<'\n';
    }
}
void dfs(int u,int dad)
{
    color[u]=1;
    Fill(cur++,{u});
    vector<int>que;
    for(int v:adj[u])
    {
        if(v!=dad)
        {
            if(color[v])
            {
                if(depth[v]<depth[u])que.push_back(v);
            }
            else
            {
                depth[v]=depth[u]+1;
                //cout<<u<<' '<<v<<'\n';
                dfs(v,u);
                Fill(cur++,{u});
            }
        }
    }
    if(que.empty())que.push_back(u);
    Fill(cur++,que);
    Fill(cur++,{u});
}
vector<vector<int>> create_map(int N,int m,vector<int>u,vector<int>v)
{
    n=N;
    cur=0;
    for(int i=1;i<=n;i++)
    {
        color[i]=0;
        adj[i].clear();
    }
    for(int i=0;i<m;i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    for(int i=1;i<=n;i++)
    {
        sort(adj[i].begin(),adj[i].end());
        adj[i].erase(unique(all(adj[i])),adj[i].end());
    }
    res=vector<vector<int>>(2*n,vector<int>(2*n,0));
    dfs(1,0);
    return res;
}

• 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