Submission #1155045

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

island

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

map<pii,ll> LOG;

ll QRY(ll v, ll k) {
    if (LOG.find({v,k})==LOG.end()) {
        LOG[{v,k}]=query(v+1,k);
    }
    return LOG[{v,k}];
}

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;
    }
}

set<pii> cedg;

void ANS(ll x, ll y) {
    if (cedg.find({x,y})!=cedg.end()) {
        return;
    }
    cedg.insert({x,y});
    cedg.insert({y,x});
    answer(x+1,y+1);
    fz(x,y);
}

void solve(int N, int L) {
    ll f1[N];
    for (ll i=0;i<N;i++) {
        f1[i]=QRY(i,1)-1;
    }
    vector<bool> frz(N,false); //frozen?
    for (ll i=0;i<N;i++) {
        if (f1[i]<i && f1[f1[i]]!=i) {
            ANS(i,f1[i]);
        } else if (f1[i]<i && f1[f1[i]]==i) {
            ANS(i,f1[i]);
            ll a1 = QRY(i,2)-1;
            ll a2 = QRY(f1[i],2)-1;
            if (a1==a2) {
                assert(a1>f1[i]);
                if (a1<i) {
                    frz[f1[i]]=1;
                    ANS(i,a1);
                } else {
                    frz[i]=1;
                    frz[f1[i]]=1;
                }
            }
        } else if (f1[i]>i && f1[f1[i]]!=i) {
            ANS(f1[i],i);
            frz[i]=1;
        }
    }
    for (ll T=2;T<N;T++) {
        for (ll i=(N-1);i>=0;i--) {
            if (!frz[i]) {
                ll j = QRY(i,T);
                if (j<i) {
                    if (cedg.find({i,j})==cedg.end()) {
                        if (getf(i)==getf(j)) {
                            frz[i]=1;
                        } else {
                            ANS(i,j);
                        }
                    }
                } else {
                    if (cedg.find({i,j})==cedg.end()) {
                        if (getf(i)==getf(j)) {
                            frz[i]=1;
                        } else {
                            ANS(i,j);
                        }
                    }
                    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