Submission #1243107

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

longesttrip

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

using namespace std;

const int maxn = 300;

int n;
int dist[maxn];
int e[maxn][maxn];
queue <int> q;

int bfs(int poc){
    q.push(poc);
    memset(dist, -1, sizeof dist);
    dist[poc] = 0;

    while(!q.empty()){
        int x = q.front();
        q.pop();

        for(int x2 = 0; x2 < n; x2++){
            if(x2 == x || !e[x][x2] || dist[x2] != -1) continue;

            dist[x2] = dist[x] + 1;
            q.push(x2);
        }
    }

    int naj = 0;

    for(int i = 0; i < n; i++){
        if(dist[i] > dist[naj]){
            naj = i;
        }
    }

    return naj;
}

vector<int> longest_trip(int N, int d){
    n = N;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; i < n; i++){
            e[i][j] = e[j][i] = are_connected({i}, {j});
        }
    }

    vector <int> v;

    int x = bfs(bfs(0));
    v.push_back(x);

    while(dist[x] > 0){
        for(int x2 = 0; x2 < n; x2++){
            if(e[x2][x] && dist[x2] + 1 == dist[x]){
                x = x2;
                break;
            }
        }

        v.push_back(x);
    }

    for(int i = 0; i < n; i++){
        if(dist[i] == -1){
            x = bfs(bfs(i));
            break;
        }
    }

    if(dist[x] + 1 > v.size()){
        v.clear();
        v.push_back(x);

        while(dist[x] > 0){
            for(int x2 = 0; x2 < n; x2++){
                if(e[x2][x] && dist[x2] + 1 == dist[x]){
                    x = x2;
                    break;
                }
            }

            v.push_back(x);
        }
    }

    return v;
}

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