제출 #1315436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315436		ezzzay	세계 지도 (IOI25_worldmap)	C++20	0 / 100	1 ms	412 KiB

worldmap

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

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u = A[i] - 1, v = B[i] - 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<int>> paths;
    vector<vector<int>> used(N, vector<int>(N, 0));

    // mark edges
    for (int i = 0; i < M; i++) {
        int u = A[i] - 1, v = B[i] - 1;
        used[u][v] = used[v][u] = 1;
    }

    // extract paths
    while (true) {
        int start = -1;
        for (int i = 0; i < N; i++) {
            for (int j : adj[i]) {
                if (used[i][j]) {
                    start = i;
                    break;
                }
            }
            if (start != -1) break;
        }
        if (start == -1) break;

        vector<int> path;
        int cur = start, prev = -1;

        while (true) {
            path.push_back(cur);
            int nxt = -1;
            for (int v : adj[cur]) {
                if (v != prev && used[cur][v]) {
                    nxt = v;
                    break;
                }
            }
            if (nxt == -1) break;
            used[cur][nxt] = used[nxt][cur] = 0;
            prev = cur;
            cur = nxt;
        }

        paths.push_back(path);
    }

    int rows = N;
    int cols = max(1, (int)paths.size());
    int K = max(rows, cols);

    vector<vector<int>> grid(K, vector<int>(K, 1));

    // place each path in a column
    for (int c = 0; c < (int)paths.size(); c++) {
        for (int r = 0; r < (int)paths[c].size(); r++) {
            grid[r][c] = paths[c][r] + 1;
        }
    }

    // ensure every country appears
    for (int i = 0; i < N; i++) {
        grid[i][0] = i + 1;
    }

    return grid;
}

• 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