Submission #1243148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243148		nvujica	Longest Trip (IOI23_longesttrip)	C++20	0 / 100	1082 ms	408 KiB

longesttrip

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

using namespace std;

const int dosta = 1e5;

vector<int> longest_trip(int n, int d){
    srand(time(0));

    vector <int> v;
    for(int i = 0; i < n; i++) v.push_back(i);

    for(int i = 0; i < dosta; i++){
        int p1 = rand() % n;
        int p2 = rand() % n;

        if(p1 != p2) swap(v[p1], v[p2]);
    }

    vector <int> a, b;

    a.push_back(v[0]);

    for(int i = 1; i < n; i++){
        //if(rand() % 2) swap(a, b);
        
        if(are_connected({a.back()}, {v[i]})) a.push_back(v[i]);
        else if(b.empty() || are_connected({b.back()}, {v[i]})) b.push_back(v[i]);
        else {
            while(!b.empty()){
                a.push_back(b.back());
                b.pop_back();
            }
            b.push_back(v[i]);
        }
    }

    if(a.size() < b.size()) swap(a, b);

    return a;
}

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