제출 #1312259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312259		regulardude6	세계 지도 (IOI25_worldmap)	C++20	100 / 100	31 ms	4240 KiB

worldmap

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

static vector<vector<int>> adj;
static vector<int> vis, instk, dep, tin, tout, euler;
static vector<vector<int>> push_at;

static void dfs(int u, int p){
    tin[u] = (int)euler.size();
    euler.push_back(u);
    vis[u] = 1;
    instk[u] = 1;

    for(int v : adj[u]){
        if(v == p) continue;
        if(!vis[v]){
            dep[v] = dep[u] + 1;
            dfs(v, u);
            euler.push_back(u);
        }else{
            if(!instk[v]){
                push_at[tin[v]].push_back(dep[u]);
            }
        }
    }

    tout[u] = (int)euler.size();
    instk[u] = 0;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    adj.assign(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);
    }

    vis.assign(N, 0);
    instk.assign(N, 0);
    dep.assign(N, 0);
    tin.assign(N, 0);
    tout.assign(N, 0);
    euler.clear();
    push_at.assign(2 * N, {});

    dfs(0, -1);

    int K = 2 * N;
    vector<vector<int>> grid(K, vector<int>(K, 0));

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    stable_sort(ord.begin(), ord.end(), [&](int x, int y){ return dep[x] < dep[y]; });

    for(int u : ord){
        int r0 = 2 * dep[u];
        for(int r = r0; r < K; r++){
            for(int c = tin[u]; c < tout[u]; c++){
                grid[r][c] = u;
            }
        }
    }

    for(int c = 0; c < K; c++){
        auto &v = push_at[c];
        if(v.empty()) continue;
        sort(v.begin(), v.end());

        int j = 0;
        while(j < (int)v.size()){
            int k = j + 1;
            while(k < (int)v.size() && v[k] == v[k - 1] + 1) k++;

            int lastd = v[k - 1];
            int rr = 2 * lastd + 2;
            if(0 <= rr && rr < K) grid[rr][c] = grid[rr - 1][c];

            for(int t = j; t < k; t++){
                int d = v[t];
                int r = 2 * d + 1;
                if(0 <= r && r < K && c < (int)euler.size()) grid[r][c] = euler[c];
            }

            j = k;
        }
    }

    for(int r = 0; r < K; r++){
        for(int c = 0; c < K; c++){
            grid[r][c] += 1;
        }
    }
    return grid;
}

• 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