제출 #1273403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273403		AksLolCoding	세계 지도 (IOI25_worldmap)	C++17	100 / 100	24 ms	4356 KiB

worldmap

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

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
    int k = 2*n;
    vector ans(k, vector<int>(k));

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u = --a[i], v = --b[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<array<int, 2>>> diags(2*k-1);
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            diags[i+j].push_back({i, j});
        }
    }

    int curd = 0;

    auto filld = [&](int x, vector<int> y) {
        int dsz = diags[curd].size(), ysz = y.size();
        assert(curd < diags.size());
        assert(ysz <= dsz);
        for (int i = 0; i < dsz; i++) {
            auto [a, b] = diags[curd][i];
            if (i < ysz) ans[a][b] = y[i]+1;
            else ans[a][b] = x+1;
        }
        curd++;
    };

    vector<int> d(n, -1);
    d[0] = 0;
    
    function<void(int)> dfs = [&](int i) {
        vector<int> back;
        for (int j : adj[i]) {
            if (d[j] != -1) assert(d[j] < d[i]), back.push_back(j);
        }
        assert(back.size() <= d[i]);
        filld(i, {});
        filld(i, back);
        filld(i, {});
        for (int j : adj[i]) {
            if (d[j] != -1) continue;
            d[j] = d[i] + 1;
            dfs(j);
            filld(i, {});
        }
    };

    dfs(0);

    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: 56 / 56