Submission #1251468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251468		InternetPerson10	World Map (IOI25_worldmap)	C++20	93 / 100	25 ms	3004 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;
        // take x out from ch
        vector<int> v2;
        v2.clear();
        for(int g : adj[ch]) {
            if(g != x) v2.push_back(g);
        }
        adj[ch] = v2;
        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) {
    map_diag.clear();
    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]);
    }
    for(int i = 1; i <= N; i++) {
        sort(adj[i].begin(), adj[i].end());
    }
    dfs(1);
    // generate the map
    vis.clear();
    int min_map_diag_size = 0;
    int k = 0;
    int m = path.size();
    // cerr << "Path: ";
    // for(int g : path) cerr << g << ' ';
    // cerr << endl;
    while(vis.size() < N-1 || k < m) {
        int x = path[k%m];
        // cerr << "Now map diag has " << map_diag.size() << " and vis has " << vis.size() << endl;
        // cerr << "our new k is " << k << " and our x is " << x << endl;
        map_diag.push_back({0, {x}});
        if(k >= (int)adj[x].size()-2 && vis.count(x) == 0 && x != 1) {
            if(adj[x].size()) {
                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++;
    }
    // cerr << "Map diag:\n";
    // for(auto [p, v] : map_diag) {
    //     cerr << p << " | ";
    //     for(int g : v) cerr << g << ' ';
    //     cerr << '\n';
    // }
    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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 49 / 56