Submission #1288759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288759		ecen30	World Map (IOI25_worldmap)	C++20	0 / 100	3 ms	576 KiB

worldmap

//test ai
// worldmap.h  (the header expected by the judge)
#include <bits/stdc++.h>
using namespace std;

class WorldMap {
    int N;
    vector<vector<int>> G, T, back;          // G = original, T = tree, back = back-edges from a node
    vector<int> tin, longest, depth;
    int timer = 0;

    // ---------- DFS that builds the tree ----------
    pair<int,int> dfsTree(int v, int par) {
        tin[v] = timer++;
        int maxChild = -1, maxLen = -1;
        for (int u : G[v]) {
            if (u == par) continue;
            if (tin[u] == -1) {               // forward edge → tree edge
                T[v].push_back(u);
                depth[u] = depth[v] + 1;
                auto [len, far] = dfsTree(u, v);
                if (len > maxLen) {
                    maxLen = len;
                    maxChild = u;
                }
            } else if (tin[u] > tin[v]) {     // back-edge (upwards in DFS order)
                back[v].push_back(u);
            }
        }
        longest[v] = maxChild;
        return {1 + maxLen, maxChild == -1 ? v : longest[v]};
    }

    // ---------- layout ----------
    vector<vector<int>> layout;
    int rows = 0;               // current number of used rows
    const int COLS = 0;         // will be set to 3*N later

    void addRow(int a, int b) {                 // a left column, b right column
        for (int c = 0; c < COLS; ++c)
            layout[rows][c] = ((c & 1) ? b : a);
        ++rows;
    }

    void addBackRow(int v) {                    // insert back-edges of v on the right side
        int pos = 0;
        for (int c = 0; c < COLS; ++c) {
            if (layout[rows-1][c] == v && pos < (int)back[v].size())
                layout[rows][c] = back[v][pos++];
            else
                layout[rows][c] = v;
        }
        ++rows;
    }

    void placeChildren(int v) {
        // first the back-edges (if any)
        if (!back[v].empty()) addBackRow(v);

        // all children except the longest one
        for (int u : T[v]) if (u != longest[v]) {
            addRow(v, u);
            placeChildren(u);
            if (u != longest[v]) addRow(v, u);   // close the branch
        }

        // longest child
        if (longest[v] != -1) {
            addRow(v, longest[v]);
            placeChildren(longest[v]);
            if (T[longest[v]].size() > 0) addRow(v, longest[v]);
        }
    }

public:
    vector<vector<int>> create_map(int _N, int M, vector<int> A, vector<int> B) {
        N = _N;
        if (N == 1) return {{1}};

        // ----- build graph -----
        G.assign(N, {});
        for (int i = 0; i < M; ++i) {
            int u = A[i]-1, v = B[i]-1;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        // ----- DFS tree -----
        T.assign(N, {});
        back.assign(N, {});
        tin.assign(N, -1);
        longest.assign(N, -1);
        depth.assign(N, 0);

        // start from node 0, find a diameter end-point
        dfsTree(0, -1);
        int endpoint = dfsTree(0, -1).second;   // second call finds the real far node

        // reset for the real layout
        T.assign(N, {}); back.assign(N, {});
        tin.assign(N, -1); longest.assign(N, -1); depth.assign(N, 0);
        timer = 0;
        dfsTree(0, -1);                        // now the tree is rooted at 0, endpoint is far

        // ----- allocate the big matrix -----
        const int MAX = 3 * N;
        layout.assign(MAX, vector<int>(MAX, 0));
        rows = 0;

        // start the layout from the root
        addRow(0, longest[0]);                 // first row: root – longest child
        placeChildren(0);

        // ----- trim to smallest square -----
        int K = max(rows, 1);
        while (K * K < N) ++K;                 // at least one cell per country
        K = min(K, MAX);
        vector<vector<int>> ans(K, vector<int>(K, 0));

        // copy the used part (rows × MAX) into the square
        for (int r = 0; r < K && r < rows; ++r)
            for (int c = 0; c < K; ++c)
                ans[r][c] = layout[r][c] + 1;   // countries are 1-based

        // fill the rest with a high-degree country (any is fine)
        int filler = 0;                     // country 1
        for (int r = 0; r < K; ++r)
            for (int c = 0; c < K; ++c)
                if (ans[r][c] == 0) ans[r][c] = filler + 1;

        return ans;
    }
};

// -------------------------------------------------
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    WorldMap solver;
    return solver.create_map(N, M, A, B);
}

• 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