oj.uz

Submission #840550

# Submission time Handle Problem Language Result Execution time Memory
840550 2023-08-31T13:43:30 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 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)
{
    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;
    }

    dfs(mx, 1);
    bool split = false;
    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);
        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);
    res.push_back(v);
    vector < int > bk = construct(dx);
    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);
    return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 2 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 10 ms 324 KB Output is correct
2 Correct 28 ms 368 KB Output is correct
3 Correct 141 ms 580 KB Output is correct
4 Correct 502 ms 1000 KB Output is correct
5 Correct 775 ms 1668 KB Output is correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 33 ms 336 KB Output is correct
8 Correct 170 ms 612 KB Output is correct
9 Correct 431 ms 876 KB Output is correct
10 Correct 923 ms 1716 KB Output is correct
11 Correct 972 ms 1700 KB Output is correct
12 Execution timed out 1127 ms 1684 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 336 KB Output is correct
2 Correct 40 ms 448 KB Output is correct
3 Correct 159 ms 580 KB Output is correct
4 Correct 469 ms 1000 KB Output is correct
5 Execution timed out 1082 ms 1672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 320 KB Output is correct
2 Correct 27 ms 368 KB Output is correct
3 Partially correct 146 ms 580 KB Output is partially correct
4 Partially correct 509 ms 1004 KB Output is partially correct
5 Partially correct 919 ms 1672 KB Output is partially correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 41 ms 340 KB Output is correct
8 Partially correct 149 ms 664 KB Output is partially correct
9 Partially correct 418 ms 876 KB Output is partially correct
10 Partially correct 907 ms 1668 KB Output is partially correct
11 Partially correct 836 ms 1700 KB Output is partially correct
12 Partially correct 809 ms 1664 KB Output is partially correct
13 Execution timed out 1107 ms 1688 KB Time limit exceeded
14 Halted 0 ms 0 KB -