Submission #850191

#	Time	Username	Problem	Language	Result	Execution time	Memory
850191		CodePlatina	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	855 ms	2036 KiB

longesttrip

#include "longesttrip.h"
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

vector<int> gph[404];
bool chc[404];
bool vst[404];

void dfs(int x)
{
    vst[x] = true;
    for(auto y : gph[x]) if(chc[y] && !vst[y]) dfs(y);
}

vector<vector<int>> cmpn(int N)
{
    fill(vst, vst + N, false);
    for(int i = 0; i < N; ++i) if(chc[i]) { dfs(i); break; }

    vector<int> r1, r2;
    for(int i = 0; i < N; ++i) if(chc[i])
    {
        if(vst[i]) r1.push_back(i);
        else r2.push_back(i);
    }

    if(r2.empty()) return {r1};
    else return {r1, r2};
}

vector<int> longest_trip(int N, int d)
{
    for(int i = 0; i < N; ++i) gph[i].clear();
    fill(chc, chc + N, true); 

    for(int i = 0; i < N; ++i)
    {
        for(int j = i + 1; j < N; ++j)
        {
            if(are_connected(vector<int>{i}, vector<int>{j}))
            {
                gph[i].push_back(j);
                gph[j].push_back(i);
            }
        }
    }

    auto V = cmpn(N);
    if(V.size() == 2)
    {
        if(V[0].size() < V[1].size()) swap(V[0], V[1]);
        return V[0];
    }

    int x;
    for(int i = 0; i < N; ++i)
    {
        chc[i] = false;
        if(cmpn(N).size() == 1)
        {
            x = i;
            break;
        }
        chc[i] = true;
    }

    vector<int> ret{x};
    for(int k = 1; k < N; ++k)
    {
        for(auto i : gph[x]) if(chc[i])
        {
            chc[i] = false;
            if(cmpn(N).size() == 1)
            {
                x = i;
                ret.push_back(x);
                break;
            }
            chc[i] = true;
        }
    }

    return ret;
}

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