Submission #1223150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223150		nikd	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	337 ms	740 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#include <iterator>
using namespace std;

std::vector<int> longest_trip(int n, int D)
{
    vector<vector<bool>> mt(n, vector<bool>(n));
    vector<vector<int>> adj(n);
    for(int i = 0; i<n; i++){
        for(int j = i+1; j<n; j++){
            if(are_connected({i}, {j})){
                mt[i][j] = 1;
                mt[j][i] = 1;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // D = 1 :D

    //vedo se ci sono due cc (ez dfs)
    // poi devo togliere questo pezzo
    vector<bool> vis(n, 0);
    function<void(int)> dfs = [&](int v){
        vis[v] = 1;
        for(int u: adj[v]){
            if(vis[u]) continue;
            dfs(u);
        }
    };
    dfs(0);
    int cnt = 0;
    for(int i = 0; i<n; i++) cnt += vis[i];
    if(cnt != n){
        vector<int> sol;
        if(cnt >= (n+1)/2){
            for(int i= 0; i<n; i++) if(vis[i]) sol.push_back(i);
        }
        else{
            for(int i= 0; i<n; i++) if(!vis[i]) sol.push_back(i);
        }
        return sol;
    }
    //trovo due non collegati
    vector<int> first;
    vector<int> second;
    for(int i = 0; i<n; i++){
        for(int j = i+1; j<n; j++){
            if(!mt[i][j]){
                first.push_back(i);
                second.push_back(j);    
                i = n; break;        
            }
        }
    }
    if(first.empty()){
        vector<int> sol(n);
        iota(sol.begin(), sol.end(), 0);
        return sol;
    }
    //ciclo sugli altri e dvido in tre array
    vector<int> md;
    for(int i = 0; i<n; i++){
        if(i == first[0] || i == second[0]) continue;
        bool b1 = mt[i][first[0]];
        bool b2 = mt[i][second[0]];
        if(b1 && b2) md.push_back(i);
        else if(b1) first.push_back(i);
        else if(b2) second.push_back(i);
        else assert(0);
    }
    //separo a metà quelli in mezzzo 
    if(md.size()){
        vector<int> md1 = {md[0]};
        vector<int> md2;
        for(int i = 1; i<md.size(); i++){
            if(mt[md[0]][i]) md1.push_back(i);
            else md2.push_back(i);
        }

        //assegno le due metà

        for(int i: first){
            if(!mt[i][md1[0]]){
                swap(md1, md2);
                break;
            }
        }

        
        for(int i: md1) first.push_back(i);
        for(int i: md2) second.push_back(i);
    }

    //visito cricca sx a partire da uno in mezzo e visito cricca dx allo stesso modo

    for(int i: first){
        for(int j: second){
            if(mt[i][j]){
                vector<int> sol;
                for(int i_:first){
                    if(i_ == i) continue;
                    sol.push_back(i_);
                }
                sol.push_back(i);
                sol.push_back(j);
                for(int i_:second){
                    if(i_==j) continue;
                    sol.push_back(i_);
                }
                return sol;
            }
        }
    }
    assert(0);

}

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