Submission #982111

#	Time	Username	Problem	Language	Result	Execution time	Memory
982111		someone	Island Hopping (JOI24_island)	C++17	100 / 100	6 ms	1732 KiB

island

#include "island.h"
#include <iostream>
using namespace std;

const int M = 342;

int par[M], n;
bool adj[M][M], reported[M][M], found[M];

int F(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F(par[i]);
}

void U(int a, int b) {
    par[F(a)] = F(b);
}

void add(int x, int y) {
    U(x, y);
    adj[x][y] = adj[y][x] = true;
    if(!reported[x][y]) {
        answer(x, y);
        reported[x][y] = reported[y][x] = true;
    }
}

void solve(int n, int l) {
    for(int i = 1; i <= n; i++)
        par[i] = i;
    for(int i = 2; i <= n; i++) {
        int k = 1, nxt = query(i, k);
        while(k < n && nxt < i && F(i) != F(nxt)) {
            add(i, nxt);
            k++;
            if(k < n) nxt = query(i, k);
        }
    }
}

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