oj.uz

Submission #840648

# Submission time Handle Problem Language Result Execution time Memory
840648 2023-08-31T14:56:58 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
5 / 100
 959 ms 884 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 > ans[maxn];
void 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)
    {
        ans[v].push_back(v);
        return;
    }

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

    int var = -1, dar = viable[0];
    for (int u : viable)
    {
        if (used[u] == 0)
            {
                construct(u);
                var = u;
            }
    }

    if (var == -1)
    {
        swap(ans[v], ans[dar]);
        ans[v].push_back(v);
        return;
    }

    if (ans[var].size() > ans[dar].size())
        swap(var, dar);
    swap(ans[v], ans[var]);
    ans[v].push_back(v);
    for (int u : ans[dar])
        ans[v].push_back(u);
    //if (r2.size() > res.size())
      //  res = r2;
    //res.push_back(v);
    return;
}
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(), ans[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;
    construct(0);

    return ans[0];
}

Compilation message

longesttrip.cpp: In function 'void 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 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 1 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 240 KB Output is correct
2 Correct 30 ms 208 KB Output is correct
3 Correct 209 ms 336 KB Output is correct
4 Correct 540 ms 432 KB Output is correct
5 Correct 959 ms 772 KB Output is correct
6 Incorrect 0 ms 208 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 208 KB Output is correct
2 Correct 23 ms 208 KB Output is correct
3 Correct 179 ms 344 KB Output is correct
4 Correct 373 ms 432 KB Output is correct
5 Correct 807 ms 884 KB Output is correct
6 Incorrect 1 ms 208 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 28 ms 208 KB Output is correct
3 Partially correct 217 ms 336 KB Output is partially correct
4 Partially correct 482 ms 436 KB Output is partially correct
5 Partially correct 836 ms 864 KB Output is partially correct
6 Incorrect 1 ms 208 KB Incorrect
7 Halted 0 ms 0 KB -