Submission #1266138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266138		Sharky	World Map (IOI25_worldmap)	C++20	12 / 100	19 ms	1352 KiB

worldmap

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

bool vis[41];
vector<int> adj[41];
vector<pair<int, int>> ord;
int deg[41], jp[41], kp[41];
set<pair<int, int>> st;

void dfs(int u) {
    vis[u] = 1;
    for (auto& v : adj[u]) {
        if (!vis[v]) {
            st.insert({u, v});
            ord.push_back({v, 0});
            dfs(v);
            ord.push_back({v, 1});
        }
    }
}

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {

    for (int i = 0; i <= 40; i++) vis[i] = 0, adj[i].clear(), deg[i] = 0, jp[i] = 100, kp[i] = 0;
    ord.clear();
    st.clear();
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    ord.push_back({1, 0});
    dfs(1);
    while (ord.size() < 4 * N - 1) ord.push_back({1, 1});
    std::vector<std::vector<int>> ans(2 * N, std::vector<int>(2 * N, 1));
    int p = 0, cnt = 0;
    for (auto& [x, y] : ord) {
        if (!y) {
            cnt++;
            for (int i = p; i < p + 3 - !!(cnt == N); i++) {
                for (int j = 0; j < 2 * N; j++) {
                    int k = i - j;
                    if (k >= 0 && k < 2 * N) {
                        ans[j][k] = x;
                        if (i == p + 1) deg[x]++, jp[x] = min(jp[x], j); kp[x] = max(kp[x], k);
                    }
                }
            }
            p += 3 - !!(cnt == N);
        } else {
            for (int j = 0; j < 2 * N; j++) {
                int k = p - j;
                if (k >= 0 && k < 2 * N) ans[j][k] = x;
            }
            p++;
        }
    }
    for (int i = 0; i < M; i++) {
        if (st.count({A[i], B[i]}) || st.count({B[i], A[i]})) continue;
        if (deg[A[i]] < deg[B[i]]) swap(A[i], B[i]);
        deg[A[i]]--, ans[jp[A[i]]++][kp[A[i]]--] = B[i];
    }

    return ans;
}

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