제출 #1332449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332449		2sqrt3	Island Hopping (JOI24_island)	C++20	2 / 100	211 ms	1020 KiB

island

#include "island.h"
#include <vector>

using namespace std;

void solve(int N, int L) {
    // 记录节点是否已经被加入到我们已知的树网络中
    vector<bool> vis(N + 1, false);
    vis[1] = true; // 初始以节点 1 为基准点

    for (int i = 2; i <= N; ++i) {
        if (vis[i]) continue;
        
        int curr = i;
        vector<int> track;
        
        // 从当前节点出发，不断向节点 1 走，直到碰到已经访问过的节点
        while (!vis[curr]) {
            track.push_back(curr);
            curr = query(curr, 1);
        }
        
        // 此时 curr 已经是连通的已知节点。
        // 我们只需沿着刚才记录的路径倒推回去，把边连上即可。
        int parent = curr;
        while (!track.empty()) {
            int u = track.back();
            track.pop_back();
            
            answer(u, parent);
            vis[u] = true; // 标记沿途的节点为已访问
            parent = u;    // 继续向上连接
        }
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 9
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 22
• Subtask 8: 0 / 28