Submission #1225440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225440		mariaclara	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	6 ms	440 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second

int rand(int a, int b) {
    return rand()%(b-a+1) + a;
}

int n;
vi pai;
vector<vi> comp;

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

int join(int x, int y) {
    if(x == -1) return y;

    x = find(x);
    y = find(y);

    if(x == y) return x;

    if(sz(comp[x]) > sz(comp[y])) swap(x,y);

    pai[x] = y;
    for(auto it : comp[x]) comp[y].pb(it);
    comp[x].clear();

    return y;
}

int find_edge(int X, vi &out) {
    int click = -1, C = -1;
    
    random_shuffle(all(out));

    for(auto A : out) {
        if(are_connected({X}, comp[A])) {
            C = A;
            break;
        }
        else click = join(click, A);
    }

    for(int i = 0; i < sz(out); i++) {
        if(pai[out[i]] != out[i] or out[i] == C)
            out.erase(out.begin() + i), i--;
    }

    if(C == -1) return -1;

    int l = 0, r = sz(comp[C]) - 1;

    while(l < r) {
        int mid = (l+r)/2;

        vi aux;
        for(int i = l; i <= mid; i++)
            aux.pb(comp[C][i]);

        if(are_connected({X}, aux)) r = mid;
        else l = mid+1;
    }

    l = comp[C][l];
    pai[C] = l;
    swap(comp[l], comp[C]);
    pai[l] = l;

    return l;
}

vi longest_trip(int N, int D) {
    srand(93652);
    n = N;

    pai.clear();
    pai.resize(N);
    comp.clear();
    comp.resize(N);

    vi cam = {rand(0, N-1)};
    vi out;

    for(int i = 0; i < N; i++) {
        pai[i] = i; 
        comp[i].pb(i);
        if(i != cam[0]) out.pb(i); // randomizar
    }

    while(sz(cam) < N) {
        int A = find_edge(cam.back(), out);

        if(A != -1) {
            cam.pb(A);
            for(auto it : comp[A])
                if(it != A) cam.pb(it);
            continue;
        }

        vi out_cam;
        for(auto C : out) {
            for(auto it : comp[C]) 
                out_cam.pb(it);
        }

        if(!are_connected(cam, out_cam)) {
            if(sz(cam) >= sz(out_cam)) return cam;
            return out_cam;
        }

        int l = 0, r = sz(cam) - 2;
        while(l < r) {
            int mid = (l+r)/2;

            vi aux;
            for(int i = l; i <= mid; i++)
                aux.pb(cam[i]);

            if(are_connected(aux, out_cam)) r = mid;
            else l = mid+1;
        }

        l = cam[l];

        while(cam[0] != l) {
            cam.pb(cam[0]);
            cam.erase(cam.begin());
        }

        reverse(all(cam));
    }

    return cam;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60