Submission #843896

#	Time	Username	Problem	Language	Result	Execution time	Memory
843896		LucaIlie	Longest Trip (IOI23_longesttrip)	C++17	30 / 100	773 ms	2284 KiB

longesttrip

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

using namespace std;

const int MAX_N = 256;
bool vis[MAX_N];
vector<int> edges[MAX_N];
vector<int> best, ans;

int getEdge( int u ) {
    vector<int> x;
    for ( int v: edges[u] ) {
        if ( !vis[v] )
            x.push_back( v );
    }

    if ( x.size() == 0 )
        return -1;
    return x[rand() % x.size()];
}

vector<int> longest_trip( int n, int d ) {
    for ( int u = 0; u < n; u++ ) {
        edges[u].clear();
        vis[u] = false;
    }

    for ( int u = 0; u < n; u++ ) {
        for ( int v = u + 1; v < n; v++ ) {
            int x = are_connected( { u }, { v } );
            if ( x ) {
                edges[u].push_back( v );
                edges[v].push_back( u );
            }
        }
    }

    best.clear();
    for ( int s = 0; s < n; s++ ) {
        int u = s;
        ans.clear();
        ans.push_back( u );
        vis[u] = true;

        int v = getEdge( u );
        while ( v >= 0 ) {
            ans.push_back( v );
            vis[v] = true;

            u = v;
            v = getEdge( u );
        }
        if ( ans.size() > best.size() )
            best = ans;
    }

    return best;
}

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