제출 #1128321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128321		vladilius	Island Hopping (JOI24_island)	C++20	65 / 100	7 ms	668 KiB

island

#include <bits/stdc++.h>
#include "island.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct dsu{
    vector<int> sz, p;
    int n;
    dsu(int ns){
        n = ns;
        sz.resize(n + 1);
        p.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        sz[y] += sz[x];
        p[x] = y;
    }
};

void solve(int n, int l){
    vector<vector<int>> f(n + 1, vector<int>(n));
    vector<vector<bool>> E(n + 1, vector<bool>(n + 1));
    auto get = [&](int i, int j){
        if (!f[i][j]){
            f[i][j] = query(i, j);
        }
        return f[i][j];
    };
    vector<int> t(n + 1, 1);
    dsu T(n);
    for (int i = 1; i <= n; i++){
        while (t[i] < n){
            int v = get(i, t[i]);
            if (T.get(i) == T.get(v)){
                if (E[i][v]){
                    t[i]++;
                    continue;
                }
                break;
            }
            while (t[v] < n && get(v, t[v]) < i) t[v]++;
            if (t[v] == n || get(v, t[v]) != i) break;
            
            E[i][v] = E[v][i] = 1;
            answer(i, v);
            T.unite(i, v);
            t[i]++;
        }
    }
}

• 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