oj.uz

Submission #894699

# Submission time Handle Problem Language Result Execution time Memory
894699 2023-12-28T18:06:24 Z JeanBombeur Longest Trip (IOI23_longesttrip) C++17
15 / 100
 810 ms 1936 KB 
#include "longesttrip.h"
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

//  <|°_°|>

const int MAX_NODES = 256;

bool Edge[MAX_NODES][MAX_NODES];
vector <int> Adj[MAX_NODES];

vector <int> Path;

int Seen[MAX_NODES];

int Dfs(int node) {
    if (Seen[node])
        return 0;
    Path.push_back(node);
    int ans = Seen[node] = 1;
    for (int dest : Adj[node])
        ans += Dfs(dest);
    return ans;
}

vector <int> longest_trip(int nbNodes, int density) {
    
    for (int i = 0; i < nbNodes; i ++)
    {
        Adj[i].clear();
        fill_n(Edge[i], nbNodes, 0);
    }
    Path.clear();
    fill_n(Seen, nbNodes, 0);
    for (int i = 0; i < nbNodes; i ++)
    {
        for (int j = i + 1; j < nbNodes; j ++)
        {
            if (are_connected({i}, {j}))
            {
                Edge[i][j] = 1;
                Adj[i].push_back(j);
                Adj[j].push_back(i);
            }
        }
    }
    int n = Dfs(0);
    if (n != nbNodes)
    {
        int first = (2 * n) >= nbNodes;
        vector <int> v;
        for (int i = 0; i < nbNodes; i ++)
        {
            if (Seen[i] == first)
                v.push_back(i);
        }
        return v;
    }
    vector <int> v = {0};
    for (int a : Path)
    {
        if (!a)
            continue;
        if (Edge[v.back()][a])
            v.push_back(a);
        else if (Edge[v[0]][a])
        {
            reverse(v.begin(), v.end());
            v.push_back(a);
        }
        else
        {
            vector <int> nv;
            while (!Edge[a][v.back()])
            {
                nv.push_back(v.back());
                v.pop_back();
            }
            v.push_back(a);
            while (nv.size())
            {
                v.push_back(nv.back());
                nv.pop_back();
            }
        }
    }
    return v;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 163 ms 1596 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 104 ms 600 KB Output is correct
4 Correct 318 ms 1140 KB Output is correct
5 Correct 785 ms 1408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 27 ms 600 KB Output is correct
3 Correct 115 ms 344 KB Output is correct
4 Correct 392 ms 1372 KB Output is correct
5 Correct 770 ms 1152 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Correct 112 ms 712 KB Output is correct
9 Correct 282 ms 988 KB Output is correct
10 Correct 738 ms 1624 KB Output is correct
11 Correct 709 ms 1440 KB Output is correct
12 Correct 739 ms 1196 KB Output is correct
13 Correct 802 ms 1364 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 127 ms 856 KB Output is correct
4 Correct 375 ms 1400 KB Output is correct
5 Correct 710 ms 1784 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 121 ms 600 KB Output is correct
9 Correct 267 ms 856 KB Output is correct
10 Correct 810 ms 1608 KB Output is correct
11 Correct 779 ms 1384 KB Output is correct
12 Correct 698 ms 1364 KB Output is correct
13 Correct 734 ms 1540 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Runtime error 1 ms 344 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Partially correct 108 ms 856 KB Output is partially correct
4 Partially correct 382 ms 872 KB Output is partially correct
5 Partially correct 728 ms 1440 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Partially correct 126 ms 852 KB Output is partially correct
9 Partially correct 264 ms 1116 KB Output is partially correct
10 Partially correct 775 ms 1936 KB Output is partially correct
11 Partially correct 760 ms 1440 KB Output is partially correct
12 Partially correct 719 ms 1408 KB Output is partially correct
13 Partially correct 688 ms 1136 KB Output is partially correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Runtime error 1 ms 344 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -