oj.uz

Submission #840591

# Submission time Handle Problem Language Result Execution time Memory
840591 2023-08-31T14:12:13 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1756 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);

    }
}

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 Correct 1 ms 208 KB Output is correct
2 Correct 208 ms 856 KB Output is correct

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 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 30 ms 360 KB Output is correct
3 Correct 153 ms 604 KB Output is correct
4 Correct 433 ms 1020 KB Output is correct
5 Correct 854 ms 1636 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 31 ms 364 KB Output is correct
8 Correct 110 ms 520 KB Output is correct
9 Correct 311 ms 876 KB Output is correct
10 Correct 930 ms 1688 KB Output is correct
11 Correct 860 ms 1664 KB Output is correct
12 Correct 951 ms 1680 KB Output is correct
13 Correct 861 ms 1664 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 208 KB Output is correct
2 Correct 39 ms 368 KB Output is correct
3 Correct 159 ms 580 KB Output is correct
4 Correct 482 ms 976 KB Output is correct
5 Correct 972 ms 1568 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 32 ms 356 KB Output is correct
8 Correct 202 ms 588 KB Output is correct
9 Correct 405 ms 868 KB Output is correct
10 Correct 844 ms 1624 KB Output is correct
11 Correct 989 ms 1660 KB Output is correct
12 Execution timed out 1028 ms 1756 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 208 KB Output is correct
2 Correct 29 ms 456 KB Output is correct
3 Partially correct 182 ms 588 KB Output is partially correct
4 Partially correct 461 ms 992 KB Output is partially correct
5 Partially correct 765 ms 1640 KB Output is partially correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 29 ms 348 KB Output is correct
8 Partially correct 206 ms 544 KB Output is partially correct
9 Partially correct 275 ms 820 KB Output is partially correct
10 Partially correct 982 ms 1680 KB Output is partially correct
11 Partially correct 910 ms 1664 KB Output is partially correct
12 Partially correct 878 ms 1652 KB Output is partially correct
13 Execution timed out 1032 ms 1660 KB Time limit exceeded
14 Halted 0 ms 0 KB -