Submission #842072

#	Time	Username	Problem	Language	Result	Execution time	Memory
842072		Tenis0206	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	758 ms	2012 KiB

longesttrip

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

using namespace std;

const int nmax = 256;

int n;

std::vector<int> G[nmax + 5];

int d[nmax + 5];

bool sel[nmax + 5];
int t[nmax + 5];

int split, l1, l2;

int find_next_go(int nod)
{
    for(auto it : G[nod])
    {
        if(!sel[it])
        {
            return it;
        }
    }
    return -1;
}

void dfs(int nod)
{
    sel[nod] = true;
    int son = find_next_go(nod);
    int nr_sons = 0;
    while(son!=-1)
    {
        t[son] = nod;
        dfs(son);
        son = find_next_go(nod);
        ++nr_sons;
    }
    if(nr_sons==2)
    {
        split = nod;
    }
    if(!nr_sons)
    {
        if(l1==-1)
        {
            l1 = nod;
        }
        else
        {
            l2 = nod;
        }
    }
}

std::vector<int> solve_component(int root)
{
    dfs(root);
    vector<int> r;
    if(l2==-1)
    {
        int nod = l1;
        r.push_back(l1);
        while(nod!=root)
        {
            nod = t[nod];
            r.push_back(nod);
        }
        return r;
    }
    vector<int> a,b;
    bool ok = false;
    for(auto it : G[l1])
    {
        if(it==root)
        {
            ok = true;
        }
    }
    if(!ok)
    {
        swap(l1,l2);
    }
    int nod = l1;
    while(nod!=split)
    {
        a.push_back(nod);
        nod = t[nod];
    }
    reverse(a.begin(),a.end());
    nod = l2;
    b.push_back(nod);
    while(nod!=root)
    {
        nod = t[nod];
        b.push_back(nod);
    }
    reverse(b.begin(),b.end());
    for(auto it : a)
    {
        r.push_back(it);
    }
    for(auto it : b)
    {
        r.push_back(it);
    }
    return r;
}

std::vector<int> longest_trip(int N, int D)
{
    n = N;
    for(int i=0; i<n; i++)
    {
        G[i].clear();
        sel[i] = false;
        t[i] = -1;
    }
    split = -1, l1 = -1, l2 = -1;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(are_connected({i}, {j}))
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    vector<int> r;
    vector<int> aux = solve_component(0);
    if(aux.size() > r.size())
    {
        r = aux;
    }
    return r;
}

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