Submission #1155136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155136		Math4Life2020	Island Hopping (JOI24_island)	C++20	2 / 100	2 ms	412 KiB

island

#include "island.h"
#include <bits/stdc++.h>
using namespace std;

using ll = int; 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);
    f[a]=b;
}

set<pii> sans;

void ANS(ll a, ll b) {
    if (sans.find({a,b})!=sans.end()) {
        return;
    }
    sans.insert({a,b});
    sans.insert({b,a});
    answer(a+1,b+1);
    fz(a,b);
}

void solve(int N, int L) {
    for (ll i=0;i<N;i++) {
        f[i]=i;
    }
    ll x0[N];
    for (ll i=0;i<N;i++) {
        x0[i]=query(i+1,1)-1;
    }
    vector<bool> frz(N,0); //frozen?
    vector<bool> o2(N,0); //only round 2?
    vector<bool> odn(N,0);
    for (ll i=0;i<N;i++) {
        ANS(i,x0[i]);
        if (x0[x0[i]]==i) {
            if (i<x0[i]) {
                frz[i]=1;
                odn[x0[i]]=1;
            }
        } else if (x0[i]>i) {
            o2[i]=1;
            frz[i]=1;
        }
    }
    for (ll T=2;T<N;T++) {
        for (ll i=(N-1);i>=0;i--) {
            if (frz[i] && (T!=2 || !o2[i])) {
                ll j = query(i+1,T)-1;
                if (odn[i] && j>i) {
                    continue;
                }
                if (getf(i)!=getf(j)) {
                    ANS(i,j);
                } else {
                    if (sans.find({i,j})==sans.end()) {
                        frz[i]=1;
                    }
                }
                if (j>i) {
                    frz[i]=1;
                }
            }
        }
    }
}

• 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