oj.uz

Submission #840555

# Submission time Handle Problem Language Result Execution time Memory
840555 2023-08-31T13:46:36 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
5 / 100
 968 ms 1716 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 = 0; u < n; u ++)
    {
        if (edge[v][u] != 1)
            continue;
        if (!used[u])
            dfs(u, c);

    }
}

vector < int > construct(int v, bool done)
{
    for (int i = 0; i < n; i ++)
        used[i] = 0;
    int mx = -1;
    for (int u = 0; u < n; u ++)
    {
        if (edge[v][u] == 1)
        {
            edge[v][u] = 2, mx = u;
            edge[u][v] = 1;
        }
    }

    if (mx == -1)
    {
        vector < int > vec;
        vec.push_back(v);
        return vec;
    }bool split = false;
    if (!done)
    {dfs(mx, 1);

    for (int u = 0; u < n; u ++)
    {
        if (edge[v][u] == 2 && used[u] == 0)
        {
            split = true;
        }
        if (edge[v][u] == 2)
            edge[v][u] = 1;
    }
    }

    if (!split)
    {
        for (int u = 0; u < n; u ++)
        {
            if (edge[v][u])
            {
                edge[v][u] = edge[u][v] = 0;
            }
        }
        vector < int > res = construct(mx, true);
        res.push_back(v);
        return res;
    }

    int dx = -1;
    for (int u = 0; u < n; u ++)
    {
        if (edge[v][u])
        {
            edge[v][u] = edge[u][v] = 0;
            if (u != mx)
                dx = u;
        }
    }

    vector < int > res = construct(mx, true);
    res.push_back(v);
    vector < int > bk = construct(dx, true);
    reverse(bk.begin(), bk.end());
    for (int u : bk)
        res.push_back(u);
    return res;
}
vector<int> longest_trip(int N, int D)
{
    n = N;
    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 ++)
        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);
            edge[i][j] = 1;
            edge[j][i] = 1;
        }
    }

    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;
    }

    vector < int > res = construct(0, false);
    return res;
}

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 3 ms 256 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 0 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 22 ms 336 KB Output is correct
3 Correct 139 ms 648 KB Output is correct
4 Correct 478 ms 1004 KB Output is correct
5 Correct 968 ms 1664 KB Output is correct
6 Correct 14 ms 208 KB Output is correct
7 Incorrect 5 ms 208 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 41 ms 340 KB Output is correct
3 Correct 147 ms 584 KB Output is correct
4 Correct 282 ms 1004 KB Output is correct
5 Correct 891 ms 1664 KB Output is correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 34 ms 340 KB Output is correct
8 Correct 129 ms 588 KB Output is correct
9 Correct 384 ms 880 KB Output is correct
10 Correct 784 ms 1716 KB Output is correct
11 Correct 799 ms 1700 KB Output is correct
12 Correct 870 ms 1680 KB Output is correct
13 Correct 932 ms 1688 KB Output is correct
14 Incorrect 1 ms 208 KB Incorrect
15 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 19 ms 336 KB Output is correct
3 Partially correct 193 ms 588 KB Output is partially correct
4 Partially correct 459 ms 1004 KB Output is partially correct
5 Partially correct 835 ms 1676 KB Output is partially correct
6 Correct 10 ms 208 KB Output is correct
7 Incorrect 9 ms 208 KB Incorrect
8 Halted 0 ms 0 KB -