제출 #1257815

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

worldmap

#include "worldmap.h"
using namespace std;
#include<cassert>

int n, t=0, d=0;
std::vector<int> vis;
std::vector<std::vector<int>> ans, adj;
void fill_diag(int d, int v) {
    for (int x = 0; x < 2*n; x++) {
        int y=d-x;
        if (0<=y && y<2*n) ans[x][y]=v;
    }
}

void dfs(int v) {
    vis[v] = ++t;
    int diag = d + 1;
    d += 3;
    fill_diag(diag - 1, v);
    fill_diag(diag, v);
    fill_diag(diag + 1, v);
    int x = std::max(0, diag - 2 * n + 1);
    for (int w : adj.at(v)) {
        if (!vis.at(w)) {
            dfs(w);
            fill_diag(d, v);
            ++d;
        } else if (vis.at(w) < vis.at(v)) {
            assert(0 <= diag - x && diag - x < 2 * n);
            ans.at(x).at(diag - x) = w;
            ++x;
        }
    }
}


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

    n=N;
    ans.assign(2 * N, std::vector<int>(2 * N, 0));
    adj.assign(N+1, vector<int>());
    vis.assign(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    dfs(1);
    while (d < 4 * N) {
        fill_diag(d, 1);
        ++d;
    }
    assert(t == N);
    return ans;
}

• 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