Submission #1155144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155144		Math4Life2020	Island Hopping (JOI24_island)	C++20	100 / 100	2 ms	448 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];

// void answer(ll x, ll y) {
//     cout << x << " " <<y << "\n";
// }
// //7 4 1 6 3 2 5
// vector<pii> edges = {{6,3},{3,0},{0,5},{5,2},{2,1},{1,4}};
// ll N1 = 7;

// ll query(ll x, ll d) {
//     cout << "call query(x="<<x<<",d="<<d<<")\n";
//     x--; d--;
//     vector<ll> dist(Nm,-1);
//     dist[x]=0;
//     while(1) {
//         bool df = 0;
//         for (pii p0: edges) {
//             if (dist[p0.first]==-1 && dist[p0.second]!=-1) {
//                 dist[p0.first]=1+dist[p0.second];
//                 df = 1;
//             }
//             if (dist[p0.first]!=-1 && dist[p0.second]==-1) {
//                 dist[p0.second]=1+dist[p0.first];
//                 df = 1;
//             }
//         }
//         if (!df) {
//             break;
//         }
//     }
//     vector<pii> vc;
//     for (ll i=0;i<N1;i++) {
//         if (i!=x) {
//             vc.push_back({dist[i],i});
//         }
//     }
//     sort(vc.begin(),vc.end());
//     cout << "returning "<<(vc[d].second+1)<<"\n";
//     return (vc[d].second+1);
// }

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;
                //cout << "FREEZE i="<<i<<"\n";
                odn[x0[i]]=1;
            }
        } else if (x0[i]>i) {
            //o2[i]=1;
            frz[i]=1;
            //cout << "FREEZE i="<<i<<"\n";
        }
    }
    for (int i=0;i<N;i++) {
        if (x0[i]>i && x0[x0[i]]!=i) {
            odn[x0[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) {
                    frz[i]=1;
                    //cout << "FREEZE i="<<i<<"\n";
                    continue;
                }
                if (getf(i)!=getf(j)) {
                    ANS(i,j);
                } else {
                    if (sans.find({i,j})==sans.end()) {
                        frz[i]=1;
                        //cout << "FREEZE i="<<i<<"\n";
                    }
                }
                if (j>i) {
                    frz[i]=1;
                    //cout << "FREEZE i="<<i<<"\n";
                }
            }
        }
    }
}

• 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