oj.uz

Submission #840644

# Submission time Handle Problem Language Result Execution time Memory
840644 2023-08-31T14:52:55 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 972 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 217 ms 784 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 17 ms 332 KB Output is correct
3 Correct 131 ms 340 KB Output is correct
4 Correct 568 ms 476 KB Output is correct
5 Correct 945 ms 756 KB Output is correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 42 ms 208 KB Output is correct
8 Correct 228 ms 344 KB Output is correct
9 Correct 358 ms 440 KB Output is correct
10 Execution timed out 1010 ms 856 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 31 ms 208 KB Output is correct
3 Correct 162 ms 340 KB Output is correct
4 Correct 367 ms 468 KB Output is correct
5 Correct 958 ms 740 KB Output is correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 39 ms 208 KB Output is correct
8 Correct 202 ms 356 KB Output is correct
9 Correct 432 ms 348 KB Output is correct
10 Execution timed out 1129 ms 792 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 208 KB Output is correct
2 Correct 36 ms 208 KB Output is correct
3 Partially correct 220 ms 340 KB Output is partially correct
4 Partially correct 434 ms 476 KB Output is partially correct
5 Partially correct 902 ms 840 KB Output is partially correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 36 ms 208 KB Output is correct
8 Partially correct 171 ms 364 KB Output is partially correct
9 Partially correct 401 ms 444 KB Output is partially correct
10 Execution timed out 1018 ms 972 KB Time limit exceeded
11 Halted 0 ms 0 KB -