Submission #842085

#	Time	Username	Problem	Language	Result	Execution time	Memory
842085		Tenis0206	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	75 ms	984 KiB

longesttrip

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

using namespace std;

const int nmax = 256;

int n;

int d[nmax + 5];

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

int split, l1, l2;

int find_next_go(int nod)
{
    vector<int> l;
    for(int i=0; i<n; i++)
    {
        if(!sel[i])
        {
            l.push_back(i);
        }
    }
    if(l.empty() || !are_connected({nod},l))
    {
        return -1;
    }
    int st = 0;
    int dr = l.size();
    while(st<dr)
    {
        int mij = (st + dr) >> 1;
        vector<int> aux;
        for(int i=st; i<=mij; i++)
        {
            aux.push_back(l[i]);
        }
        if(are_connected({nod},aux))
        {
            dr = mij;
        }
        else
        {
            st = mij + 1;
        }
    }
    return l[st];
}

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)
{
    split = -1, l1 = -1, l2 = -1;
    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 = are_connected({l1}, {root});
    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++)
    {
        sel[i] = false;
        t[i] = -1;
    }
    vector<int> r;
    for(int i=0; i<n; i++)
    {
        if(sel[i])
        {
            continue;
        }
        vector<int> aux = solve_component(i);
        if(aux.size() > r.size())
        {
            r = aux;
        }
    }
    return r;
}

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