oj.uz

Submission #894700

# Submission time Handle Problem Language Result Execution time Memory
894700 2023-12-28T18:09:16 Z JeanBombeur Longest Trip (IOI23_longesttrip) C++17
15 / 100
 765 ms 1864 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] = Edge[j][i] = 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 160 ms 1432 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 114 ms 600 KB Output is correct
4 Correct 346 ms 860 KB Output is correct
5 Correct 674 ms 1184 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 18 ms 344 KB Output is correct
3 Correct 117 ms 344 KB Output is correct
4 Correct 339 ms 1492 KB Output is correct
5 Correct 697 ms 1320 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 122 ms 860 KB Output is correct
9 Correct 265 ms 856 KB Output is correct
10 Correct 700 ms 1392 KB Output is correct
11 Correct 687 ms 1620 KB Output is correct
12 Correct 701 ms 1420 KB Output is correct
13 Correct 710 ms 1752 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 122 ms 468 KB Output is correct
4 Correct 335 ms 1112 KB Output is correct
5 Correct 717 ms 1364 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 120 ms 600 KB Output is correct
9 Correct 265 ms 1112 KB Output is correct
10 Correct 702 ms 1204 KB Output is correct
11 Correct 690 ms 1552 KB Output is correct
12 Correct 725 ms 1292 KB Output is correct
13 Correct 655 ms 1648 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 10 ms 340 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 116 ms 856 KB Output is partially correct
4 Partially correct 339 ms 984 KB Output is partially correct
5 Partially correct 755 ms 1864 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Partially correct 117 ms 600 KB Output is partially correct
9 Partially correct 269 ms 856 KB Output is partially correct
10 Partially correct 715 ms 1164 KB Output is partially correct
11 Partially correct 765 ms 1340 KB Output is partially correct
12 Partially correct 722 ms 1192 KB Output is partially correct
13 Partially correct 724 ms 1676 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -