Submission #1229737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229737		vladilius	Longest Trip (IOI23_longesttrip)	C++20	60 / 100	355 ms	760 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

vector<int> longest_trip(int n, int D){
    vector<vector<bool>> d(n, vector<bool>(n));
    vector<int> g[n];
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            d[i][j] = d[j][i] = are_connected({i}, {j});
            if (d[i][j]){
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    
    vector<int> c;
    queue<int> q;
    vector<bool> used(n);
    
    vector<int> F;
    for (int i = 0; i < n; i++){
        if (used[i]) continue;
        q.push(i); used[i] = 1; c.clear();
        while (!q.empty()){
            int v = q.front(); q.pop();
            c.pb(v);
            for (int j: g[v]){
                if (!used[j]){
                    q.push(j);
                    used[j] = 1;
                }
            }
        }
        
        if (c.size() > F.size()){
            F = c;
        }
    }
    
    vector<int> out;
    vector<bool> ban(n);
    for (int i: F){
        for (int j: F){
            if (d[i][j]){
                out.pb(i);
                out.pb(j);
                ban[i] = ban[j] = 1;
                break;
            }
        }
        if (!out.empty()) break;
    }
 
    if (F.size() <= 2) return F;
    
    for (int i: F){
        if (ban[i]) continue;
        if (d[out[0]][i]){
            out.insert(out.begin(), i);
            ban[i] = 1;
            continue;
        }
    }
    
    for (int i: F){
        if (ban[i]) continue;
        if (d[out.back()][i]){
            out.pb(i);
            ban[i] = 1;
            continue;
        }
    }
    
    vector<int> ii(n);
    while (out.size() != F.size()){
        bool I = 0;
        for (int i: F){
            if (ban[i]) continue;
            if (d[i][out[0]]){
                out.insert(out.begin(), i);
                ban[i] = 1;
                I = 1;
                break;
            }
            if (d[i][out.back()]){
                out.pb(i);
                ban[i] = 1;
                I = 1;
                break;
            }
        }
        if (I) continue;
        
        assert(d[out[0]][out.back()]);
        
        for (int i = 1; i + 1 < out.size(); i++){
            int v = out[i];
            while (ii[v] < g[v].size() && ban[g[v][ii[v]]]) ii[v]++;
            if (ii[v] == g[v].size()) continue;
            int j = g[v][ii[v]];
            vector<int> nw;
            nw.pb(j);
            for (int k = i ; k < out.size(); k++){
                nw.pb(out[k]);
            }
            for (int k = 0; k < i; k++){
                nw.pb(out[k]);
            }
            out = nw;
            I = 1;
            ban[j] = 1;
            break;
        }
    }
    
    return out;
}

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