Submission #840644

#	Time	Username	Problem	Language	Result	Execution time	Memory
840644		danikoynov	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	1129 ms	972 KiB

longesttrip

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

const int maxn = 260;
vector < int > adj[maxn];
int used[maxn], edge[maxn][maxn];

int n;
void dfs(int v, int c)
{
    used[v] = c;
    for (int u : adj[v])
    {
        if (!used[u])
            dfs(u, c);

    }
}

int deg[maxn];
vector < int > construct(int v)
{
    used[v] = 1;
    vector < int > viable;
    for (int u : adj[v])
        if (!used[u])
        {
            viable.push_back(u);
            deg[u] --;
            deg[v] --;
        }

    if (viable.size() == 0)
    {
        vector < int > cur;
        cur.push_back(v);
        return cur;
    }

    for (int i = 1; i < viable.size(); i ++)
    {
        if (deg[viable[i]] < deg[viable[0]])
            swap(viable[i], viable[0]);
    }
    if (viable.size() == 1)
    {
        vector < int > res = construct(viable[0]);
        res.push_back(v);
        return res;
    }

    vector < int > r1 = construct(viable[0]), r2;
    for (int u : viable)
    {
        if (used[u] == 0)
            r2 = construct(u);
    }

    vector < int > res = r1;
    res.push_back(v);
    reverse(r2.begin(), r2.end());
    for (int u : r2)
        res.push_back(u);
    //if (r2.size() > res.size())
      //  res = r2;
    //res.push_back(v);
    return res;
}
vector<int> longest_trip(int N, int D)
{
    n = N;
    if (n == 0)
        return {};
    if (D == 3)
    {
        vector < int > r;
        for (int i = 0; i < N; i ++)
            r.push_back(i);
        return r;
    }

    for (int i = 0; i < N; i ++)
        adj[i].clear();

    for (int i = 0; i < N; i ++)
        used[i] = 0, deg[i] = 0;
    for (int i = 0; i < N; i ++)
        for (int j = i + 1; j < N; j ++)
        {
            vector < int > a, b;
            a.push_back(i);
            b.push_back(j);
            if (are_connected(a, b))
            {
                adj[i].push_back(j);
                adj[j].push_back(i);

                deg[i] ++;
                deg[j] ++;
            }
        }


    int cp = 0;
    for (int i = 0; i < N; i ++)
    {
        if (!used[i])
            dfs(i, ++ cp);
    }

    if (cp == 2)
    {

        vector < int > a, b;
        for (int i = 0; i < N; i ++)
            if (used[i] == 1)
                a.push_back(i);
            else
                b.push_back(i);
        if (a.size() > b.size())
            return a;
        return b;
    }


    for (int i = 0; i < N; i ++)
        used[i] = 0;
    vector < int > res = construct(0);


    return res;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> construct(int)':
longesttrip.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 1; i < viable.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~

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