제출 #1332446

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

island

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

using namespace std;
struct DSU {
    vector<int> parent;
    
    DSU(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            return true;
        }
        return false;
    }
    
    bool same(int i, int j) {
        return find(i) == find(j);
    }
};

void solve(int N, int L) {
    DSU dsu(N);
    vector<int> ptr(N + 1, 1);
    vector<int> path;
    path.push_back(1); 
    int edges = 0;
    while (edges < N - 1) {
        int u = path.back();
        int v = query(u, ptr[u]++);
        if (dsu.same(u, v)) {
            continue;
        }
        int comp_v = dsu.find(v);
        if (path.size() >= 2 && dsu.find(path[path.size() - 2]) == comp_v) {
            answer(u, v);
            edges++;
            dsu.unite(u, v);
            path.pop_back();
        } else {
            path.push_back(v);
        }
    }
}

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