Submission #993049

#	Time	Username	Problem	Language	Result	Execution time	Memory
993049		Muhammet	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	999 ms	3808 KiB

longesttrip

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

#define N 1505

using namespace std;

vector <int> v[N], v1;

int c[N], k, y;

bool vis[N][N], vi[N];

void dfs(int x){
    vi[x] = 1;
    if(k < c[x]) y = x;
    k = max(c[x], k);
    for(auto i : v[x]){
        if(vi[i] == 0){
            c[i] = c[x] + 1;
            dfs(i);
        }
    }
}

void df(int x){
    v1.push_back(x);
    if(c[x] == 1) return;
    for(auto i : v[x]){
        if(c[i] == c[x] - 1){
            df(i);
            break;
        }
    }
}

vector<int> longest_trip(int n, int d) {
    vector <int> a(1), b(1);
    for(int i = 0; i < n; i++) v[i].clear();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            vis[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            a[0] = i;
            b[0] = j;
            if(are_connected(a, b) and vis[i][j] == 0) {
                vis[i][j] = 1;
                vis[j][i] = 1;
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    v1.clear();
    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            vi[j] = 0;
            c[j] = 0;
        }
        k = y = 0;
        c[i] = 1;
        dfs(i);
        if(k > mx){
            mx = k;
            v1.clear();
            df(y);
        }
    }
    reverse(v1.begin(), v1.end());
    return v1;
}

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