제출 #1251047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251047		alex0152	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;

vector<int>adj[41];
bitset<41>v,u;
int order[201],cnt,poz,x,y,t[41],parc[2][241],prc,poz1;
void dfs(int node)
{
    v[node]=1;
    cnt++;
    order[cnt]=node;
    for(auto it : adj[node])
        if(!v[it])
        {
            t[it]=node;
            dfs(it);
        }
    if(node!=1)
    {
        cnt++;
        order[cnt]=t[node];
    }
}
vector<vector<int>> create_map(int n, int m,vector<int> a, vector<int> b)
{
    vector<vector<int>>mat(3*n,vector<int>(3*n));
    cnt=0;
    prc=0;
    for(int i=0; i<n*3; ++i)
    {
        prc++;
        parc[0][prc]=i;
        parc[1][prc]=0;
    }
    for(int i=1; i<n*3; ++i)
    {
        prc++;
        parc[0][prc]=n*3-1;
        parc[1][prc]=i;
    }
    v.reset();
    u.reset();
    for(int i=0; i<m; ++i)
    {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    dfs(1);
    poz1=0;
    for(int i=1;i<=n-1;++i)
    {
        poz1++;
         x=parc[0][poz1];
        y=parc[1][poz1];
        for(; x>=0 && y<n*3; --x,++y)
            mat[x][y]=order[1];
    }
    for(int i=1; i<=cnt; ++i)
    {
        poz1++;
        x=parc[0][poz1];
        y=parc[1][poz1];
        for(; x>=0 && y<n*3; --x,++y)
            mat[x][y]=order[i];

        if(!u[order[i]])
        {
            u[order[i]]=1;
            poz1++;
            x=parc[0][poz1];
            y=parc[1][poz1];
            poz=0;
            for(; x>=0 && y<n*3; --x,++y)
            {
                if(poz>=adj[order[i]].size())
                    mat[x][y]=order[i];
                else
                    mat[x][y]=adj[order[i]][poz],poz++;
            }
            x=parc[0][poz1];
            y=parc[1][poz1];
            poz1++;
            for(; x>=0 && y<n*3; --x,++y)
                mat[x][y]=order[i];
        }
    }
    for(int k=poz1+1; k<=prc; ++k)
    {
        x=parc[0][k];
        y=parc[1][k];
        for(; x>=0 && y<n*3; --x,++y)
            mat[x][y]=order[cnt];

    }
    for(int i=1; i<=n; ++i)
        adj[i].clear();
    return mat;
}

• 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