제출 #1309312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309312		orosmori	세계 지도 (IOI25_worldmap)	C++20	15 / 100	23 ms	3488 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int MAXN = 305;

int n, m;
int e[MAXN][MAXN];
vector<int> G[MAXN];
int dfn[MAXN], sz[MAXN], revv[MAXN];
vector<int> son[MAXN];
int tot;

vector<vi> emp;

void dfs(int u){
    dfn[u] = ++tot;
    revv[tot] = u;
    sz[u] = 1;
    for(int v: G[u]){
        if(dfn[v]) continue;
        dfs(v);
        sz[u] += sz[v];
        son[u].push_back(v);
    }
}

vi mergev(const vi &L, const vi &R){
    vi res = L;
    res.insert(res.end(), R.begin(), R.end());
    return res;
}

// build a block for subtree of u; len is the target width we will pad to
vector<vi> solve(int u, int len){
    // if leaf
    if(son[u].empty()) return emp;

    // s = list of neighbors inside subtree that have an edge to u but are not parent and are not direct children in tree order
    vi s;
    // nodes in dfs order between dfn[u]+1 and dfn[u]+sz[u]-1 are exactly nodes in subtree except u
    for(int i = dfn[u]+1; i <= dfn[u]+sz[u]-1; ++i){
        int v = revv[i];
        if(e[u][v]) s.push_back(v);
    }

    vector<vi> res(2 * (int)s.size());
    vi outer(1, u);
    if(u == 1){
        // root: keep a border of u
        for(auto &z: res) z.push_back(u);
    }

    for(size_t i = 0; i < s.size(); ++i){
        res[2*i].push_back(u);
        res[2*i+1].push_back(s[i]);
    }
    for(auto &z: res) if(z.back() != u) z.push_back(u);

    int j = 1; // index in res where to place child blocks
    for(int v: son[u]){
        vector<vi> cur = solve(v, len - 2 - (u==1));
        if(cur.empty()) continue;
        // ensure there is space
        while(j + (int)cur.size() + 1 > (int)res.size()) res.push_back(outer);
        if((int)res[j+1].size() >= 2 + (u==1)) j++;
        for(auto &z: cur){
            if((int)res[j].size() < 2 + (u==1)) res[j].push_back(v);
            res[j] = mergev(res[j], z);
            j++;
        }
        res[j++].push_back(u);
    }

    // check last row all u
    bool all_u = true;
    for(int id: res.back()) if(id != u) { all_u = false; break; }
    if(!all_u) res.push_back(outer);

    // pad each row to length len by repeating last element
    for(auto &z: res){
        while((int)z.size() < len) z.push_back(z.back());
    }
    return res;
}

vector<vi> create_map(int N, int M, vi A, vi B){
    n = N; m = M;
    emp.clear();
    for(int i = 1; i <= n; ++i){
        G[i].clear(); son[i].clear(); dfn[i]=sz[i]=revv[i]=0;
        for(int j = 1; j <= n; ++j) e[i][j]=0;
    }
    tot = 0;
    for(int i = 0; i < m; ++i){
        e[A[i]][B[i]] = e[B[i]][A[i]] = 1;
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    if(n == 1){
        vector<vi> ans(1, vi(1,1));
        return ans;
    }

    // run DFS from 1 (input guarantees a solution exists, graph should be connected for feasible maps)
    dfs(1);

    // solve for root with length 2*n (heuristic from editorial/accepted solutions)
    vector<vi> ans = solve(1, 2*n);
    vi base = ans.back();
    while((int)ans.size() < 2*n) ans.push_back(base);

    return ans;
}

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