Submission #1154521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154521		Math4Life2020	Island Hopping (JOI24_island)	C++20	28 / 100	3 ms	420 KiB

island

#include "island.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 305;
ll f[Nm];

ll getf(ll x) {
    if (f[x]==x) {
        return x;
    }
    return f[x]=getf(f[x]);
}

void fz(ll a, ll b) {
    a = getf(a); b = getf(b);
    if (a!=b) {
        f[a]=b;
    }
}

void solve(int N, int L) {
    for (ll i=0;i<N;i++) {
        f[i]=i;
    }
    vector<bool> frz(N,0); //frozen?
    set<pii> reg;
    for (ll T=0;T<(N-1);T++) {
        for (ll i=(N-1);i>=0;i--) {
            if (!frz[i]) {
                ll jc = query(i+1,T+1)-1;
                if (getf(jc)==getf(i)) {
                    if (reg.find({jc,i})==reg.end()) {
                        frz[i]=1;
                    }
                } else if (jc>i) {
                    answer(jc+1,i+1);
                    fz(jc,i);
                    reg.insert({i,jc});
                    reg.insert({jc,i});
                }else {
                    answer(jc+1,i+1);
                    fz(jc,i);
                }
            }
        }
    }
}

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