oj.uz

Submission #840594

# Submission time Handle Problem Language Result Execution time Memory
840594 2023-08-31T14:15:10 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 892 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 ++)
        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);
                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 : adj[tk])
        {
            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 Correct 0 ms 208 KB Output is correct
2 Correct 170 ms 832 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 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 208 KB Output is correct
2 Correct 39 ms 208 KB Output is correct
3 Correct 176 ms 368 KB Output is correct
4 Correct 440 ms 580 KB Output is correct
5 Execution timed out 1002 ms 892 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 39 ms 208 KB Output is correct
3 Correct 185 ms 364 KB Output is correct
4 Correct 531 ms 476 KB Output is correct
5 Correct 850 ms 712 KB Output is correct
6 Correct 13 ms 208 KB Output is correct
7 Correct 39 ms 316 KB Output is correct
8 Correct 169 ms 376 KB Output is correct
9 Correct 411 ms 460 KB Output is correct
10 Correct 943 ms 804 KB Output is correct
11 Correct 900 ms 736 KB Output is correct
12 Correct 852 ms 876 KB Output is correct
13 Correct 968 ms 752 KB Output is correct
14 Correct 13 ms 208 KB Output is correct
15 Correct 21 ms 208 KB Output is correct
16 Incorrect 9 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 41 ms 208 KB Output is correct
3 Partially correct 198 ms 380 KB Output is partially correct
4 Partially correct 432 ms 488 KB Output is partially correct
5 Partially correct 962 ms 720 KB Output is partially correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 20 ms 208 KB Output is correct
8 Partially correct 203 ms 336 KB Output is partially correct
9 Partially correct 310 ms 452 KB Output is partially correct
10 Partially correct 822 ms 776 KB Output is partially correct
11 Execution timed out 1035 ms 880 KB Time limit exceeded
12 Halted 0 ms 0 KB -