oj.uz

Submission #840593

# Submission time Handle Problem Language Result Execution time Memory
840593 2023-08-31T14:13:39 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1836 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> 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 ++)
        for (int j = 0; j < N; j ++)
        {
            edge[i][j] = edge[j][i] = 0;
        }
    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);
                edge[i][j] = 1;
                edge[j][i] = 1;
                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;
    }


    vector < int > res;
    int tk = 0;
    while(tk < N && deg[tk] != 1)
        tk ++;
    if (tk == N)
        tk = 0;


    for (int step = 0; step < N; step ++)
    {

        res.push_back(tk);
        int nxt = -1;
        for (int u = 0; u < N; u ++)
        {
            if (edge[tk][u])
            {
                deg[u] --;
                if (deg[u] == 1 || nxt == -1)
                    nxt = u;
                deg[tk] --;
                edge[tk][u] = edge[u][tk] = 0;
            }
        }
        tk = nxt;


    }
    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 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 336 KB Output is correct
2 Correct 32 ms 336 KB Output is correct
3 Correct 170 ms 592 KB Output is correct
4 Correct 493 ms 1016 KB Output is correct
5 Correct 946 ms 1632 KB Output is correct
6 Correct 13 ms 336 KB Output is correct
7 Correct 42 ms 368 KB Output is correct
8 Correct 149 ms 516 KB Output is correct
9 Correct 384 ms 872 KB Output is correct
10 Correct 903 ms 1672 KB Output is correct
11 Correct 843 ms 1624 KB Output is correct
12 Correct 833 ms 1644 KB Output is correct
13 Correct 903 ms 1836 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 43 ms 368 KB Output is correct
3 Correct 205 ms 584 KB Output is correct
4 Correct 547 ms 996 KB Output is correct
5 Correct 910 ms 1740 KB Output is correct
6 Correct 16 ms 260 KB Output is correct
7 Correct 43 ms 344 KB Output is correct
8 Correct 229 ms 588 KB Output is correct
9 Correct 322 ms 872 KB Output is correct
10 Correct 891 ms 1768 KB Output is correct
11 Correct 966 ms 1744 KB Output is correct
12 Correct 927 ms 1640 KB Output is correct
13 Correct 846 ms 1648 KB Output is correct
14 Incorrect 0 ms 208 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 324 KB Output is correct
2 Correct 43 ms 356 KB Output is correct
3 Partially correct 162 ms 584 KB Output is partially correct
4 Partially correct 439 ms 960 KB Output is partially correct
5 Partially correct 862 ms 1628 KB Output is partially correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 38 ms 336 KB Output is correct
8 Partially correct 151 ms 588 KB Output is partially correct
9 Partially correct 349 ms 864 KB Output is partially correct
10 Partially correct 881 ms 1684 KB Output is partially correct
11 Partially correct 910 ms 1744 KB Output is partially correct
12 Execution timed out 1010 ms 1696 KB Time limit exceeded
13 Halted 0 ms 0 KB -