Submission #1251452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251452		InternetPerson10	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

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

//  1
// 2  3
//   4 5
//
//
//   UU1U11111
//   U1U111111
//   1U1111111
//   U11111111

using namespace std;

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

vector<vector<int>> adj;

void dfs(int x) {
    path.push_back(x);
    vis.insert(x);
    for(int ch : adj[x]) {
        if(vis.count(ch)) continue;
        dfs(ch);
        path.push_back(x);
    }
}

vector<pair<int, vector<int>>> map_diag;

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);
    // generate the map
    vis.clear();
    int min_map_diag_size = 0;
    int k = 0;
    int m = path.size();
    while(vis.size() < N-1 && k < m) {
        cerr << "Now map diag has " << map_diag.size() << " and vis has " << vis.size() << endl;
        int x = path[k%m];
        map_diag.push_back({0, {x}});
        if(k >= N-3 && vis.count(x) == 0 && x != 1) {
            map_diag.push_back({1, adj[x]});
            min_map_diag_size = max(min_map_diag_size, (int)map_diag.size() + (int)map_diag.back().second.size() - 1);
            map_diag.push_back({0, {x}});
            vis.insert(x);
        }
        k++;
    }
    assert(map_diag.back().first == 0);
    while(map_diag.size() < min_map_diag_size) map_diag.push_back(map_diag.back());
    if(map_diag.size() % 2 == 0) map_diag.push_back(map_diag.back());
    int gridn = (map_diag.size() + 1) / 2;
    vector<vector<int>> ans(gridn, vector<int>(gridn));
    for(int i = 0; i < map_diag.size(); i++) {
        for(int j = 0; j < gridn; j++) {
            if(i-j < 0 || i-j >= gridn) continue;
            ans[j][i-j] = map_diag[i].second.back();
            if(map_diag[i].second.size() > 1) map_diag[i].second.pop_back();
        }
    }
    return ans;
}

• 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