Submission #1251770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251770		coding_snorlax	World Map (IOI25_worldmap)	C++20	58 / 100	175 ms	20040 KiB

worldmap

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


struct Graph {
    int n;                 // 節點數
    int m_cap;             // 最多能存的「有向邊」數 (無向圖要給 2*M)
    vector<int> head;      // head[u] = 第一條出邊的 idx，-1 代表空
    vector<int> to, nxt;   // forward-star
    int idx;               // 當前可用邊索引
    vector<char> vis;      // 拜訪標記 (0/1)
    vector<int> dfs_path;  // Euler 路徑

    /* 建構子：n 節點，m_cap = 2*M (若無向) 或 M (若有向) */
    Graph(int _n, int _max_edges)
        : n(_n), m_cap(_max_edges), head(_n + 1, -1),
          to(_max_edges), nxt(_max_edges), idx(0),
          vis(_n + 1, 0) {}

    /* 在鄰接串列前插入 (u→v) */
    void add_directed(int u, int v) {
        to[idx]   = v;
        nxt[idx]  = head[u];
        head[u]   = idx;
        ++idx;
    }
    /* 無向圖：各插一次 */
    void add_edge(int u, int v) {
        add_directed(u, v);
        add_directed(v, u);
    }

    /* DFS（Euler 路徑：進入 push，回溯再 push 原點） */
    void dfs(int u) {
        vis[u] = 1;
        dfs_path.push_back(u);
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (!vis[v]) {
                dfs(v);
                dfs_path.push_back(u);  // 回溯
            }
        }
    }
    /* 取得 DFS Euler 路徑；未連通也能處理 */
    vector<int> get_dfs_path(int root = 1) {
        fill(vis.begin(), vis.end(), 0);
        dfs_path.clear();
        dfs(root);
        for (int u = 1; u <= n; ++u)          // 若圖有多連通塊
            if (!vis[u]) dfs(u);              // 依序補 DFS
        return dfs_path;
    }

    /* 回傳 u 的鄰居 (複製一份 vector) */
    vector<int> get_neighbors(int u) const {
        vector<int> nbrs;
        for (int e = head[u]; e != -1; e = nxt[e])
            nbrs.push_back(to[e]);
        return nbrs;
    }
};


vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
 Graph g(N,2*M);
 for(int i=0;i<M;i++){
    g.add_edge(A[i],B[i]);
 }
 auto path = g.get_dfs_path(1);

  vector<vector<int>> ans(6*N-3, vector<int>(6*N-3, 1));
  for(int i=0;i<2*N-1;i++){
    for(int j=0;j<6*N-3;j++){
        ans[3*i][j] = path[i];
    }
    auto ed = g.get_neighbors(path[i]);
    int ct = 0;
    for(int j:ed){
        ans[3*i+1][ct] = j;
        ans[3*i+1][ct+1] = path[i];
        ct+=2;
    }
    for(int j=ct;j<6*N-3;j++) ans[3*i+1][j] = path[i];
    for(int j=0;j<6*N-3;j++) ans[3*i+2][j] = path[i];
  }

  return ans;
}

• 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: 14 / 56