제출 #1309476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309476		Faisal_Saqib	세계 지도 (IOI25_worldmap)	C++20	36 / 100	21 ms	3280 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)
            }
            else if(h[y]<h[x])
            {
                // last we have x
                tour.push_back(y);
                tour.push_back(x);
            }
        }
    }
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> edg0, std::vector<int> edg1)
{
    if(m*2==(n*(n-1)))
    {
        vector<vector<int>> answer(n*2,vector<int>(2*n,0));
        for(int i=0;i<2*n;i++)
        {
            if(i&1)
            {
                for(int j=0;j<2*n;j++)
                    answer[i][j]=(j%n)+1;
            }
            else{
                for(int j=0;j<2*n;j++)
                {
                    answer[i][j]=(i/2)+1;
                }
            }
        }
        return answer;
    }
    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();
    vector<vector<int>> answer(K,vector<int>(K,0));
    for(int i=0;i<K;i++)
    {
        for(int j=0;j<K;j++)
        {
            answer[i][j]=tour[i];
        }
    }
    return answer;
}

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