oj.uz

Submission #840597

# Submission time Handle Problem Language Result Execution time Memory
840597 2023-08-31T14:17:07 Z danikoynov Longest Trip (IOI23_longesttrip) C++17
15 / 100
 969 ms 760 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 260;
vector < int > adj[maxn];
int used[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);

                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 i = 0; i < N; i ++)
        used[i] = 0;
    for (int step = 0; step < N; step ++)
    {

        res.push_back(tk);
        int nxt = -1;
        used[tk] = 1;
        for (int u : adj[tk])
        {
            if (!used[u])
            {
                deg[u] --;
                if (deg[u] == 1 || nxt == -1)
                    nxt = u;
                deg[tk] --;
            }
        }
        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 265 ms 652 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 32 ms 208 KB Output is correct
3 Correct 126 ms 320 KB Output is correct
4 Correct 488 ms 332 KB Output is correct
5 Correct 952 ms 524 KB Output is correct
6 Correct 9 ms 208 KB Output is correct
7 Correct 31 ms 208 KB Output is correct
8 Correct 200 ms 324 KB Output is correct
9 Correct 294 ms 332 KB Output is correct
10 Correct 814 ms 500 KB Output is correct
11 Correct 918 ms 524 KB Output is correct
12 Correct 895 ms 496 KB Output is correct
13 Correct 969 ms 500 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 32 ms 208 KB Output is correct
3 Correct 136 ms 208 KB Output is correct
4 Correct 469 ms 340 KB Output is correct
5 Correct 885 ms 504 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 32 ms 208 KB Output is correct
8 Correct 203 ms 316 KB Output is correct
9 Correct 382 ms 436 KB Output is correct
10 Correct 892 ms 536 KB Output is correct
11 Correct 912 ms 520 KB Output is correct
12 Correct 820 ms 760 KB Output is correct
13 Correct 904 ms 556 KB Output is correct
14 Correct 8 ms 208 KB Output is correct
15 Correct 20 ms 208 KB Output is correct
16 Incorrect 11 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 34 ms 208 KB Output is correct
3 Partially correct 204 ms 208 KB Output is partially correct
4 Partially correct 441 ms 340 KB Output is partially correct
5 Partially correct 861 ms 724 KB Output is partially correct
6 Correct 9 ms 208 KB Output is correct
7 Correct 20 ms 208 KB Output is correct
8 Partially correct 181 ms 312 KB Output is partially correct
9 Partially correct 410 ms 328 KB Output is partially correct
10 Partially correct 804 ms 604 KB Output is partially correct
11 Partially correct 883 ms 604 KB Output is partially correct
12 Partially correct 872 ms 528 KB Output is partially correct
13 Partially correct 840 ms 584 KB Output is partially correct
14 Correct 10 ms 208 KB Output is correct
15 Correct 14 ms 208 KB Output is correct
16 Incorrect 8 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -