제출 #1251433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251433		InternetPerson10	세계 지도 (IOI25_worldmap)	C++20	15 / 100	18 ms	2116 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

//  1
// 2  3
//   4 5
//
//
//   111111111
//   222213333
//   111134435

using namespace std;

set<int> vis;
vector<int> path;

vector<vector<int>> adj;

void dfs(int x, int par = -1) {
    cerr << "visiting " << x << endl;
    path.push_back(x);
    if(vis.count(x)) return;
    vis.insert(x);
    if(vis.size() + 1 == adj.size()) return;
    for(int ch : adj[x]) {
        if(ch == par) continue;
        dfs(ch, x);
        path.push_back(x);
        if(vis.size() + 1 == adj.size()) return;
    }
}

vector<vector<int>> create_map(int N, int M, std::vector<int> a, std::vector<int> b) {
    vis.clear();
    vector<int>().swap(path);
    vector<vector<int>>().swap(adj);
    adj.resize(N+1);
    for(int i = 0; i < M; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    dfs(1);
    vector<vector<int>> ans(path.size());
    for(int i = 0; i < path.size(); i++) ans[i] = vector<int>(path.size(), path[i]);
    return ans;
}

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