Submission #914160

# Submission time Handle Problem Language Result Execution time Memory
914160 2024-01-21T10:06:03 Z Nelt Longest Trip (IOI23_longesttrip) C++17
30 / 100
863 ms 2636 KB
#include "longesttrip.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 256;
vv(ll) g[N];
std::vector<int> longest_trip(int n, int d)
{
    for (ll i = 0; i < n; i++)
        g[i].clear();
    vv(int) ans;
    if (d == 3)
    {
        for (ll i = 0; i < n; i++)
            ans.pb(i);
        return ans;
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (are_connected({i}, {j}))
                g[i].pb(j), g[j].pb(i);
    if (d == 1)
    {
        ll v = 0;
        bool used[n];
        for (ll i = 0; i < n; i++)
            used[i] = 0;
        for (ll i = 0; i < n; i++)
            if (g[i].size() > g[v].size())
                v = i;
        while (v != -1)
        {
            used[v] = 1;
            ans.pb(v);
            ll to = -1;
            for (ll i : g[v])
                if (!used[i] and (to == -1 or g[i].size() > g[to].size()))
                    to = i;
            v = to;
        }
    }
    else
    {
        ll v = rng() % n;
        bool used[n];
        for (ll i = 0; i < n; i++)
            used[i] = 0;
        while (v != -1)
        {
            used[v] = 1;
            ans.pb(v);
            ll to = -1;
            shuffle(allc(g[v]), rng);
            for (ll i : g[v])
                if (!used[i])
                    to = i;
            v = to;
        }
    }
    return ans;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
# 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 104 ms 856 KB Output is correct
4 Correct 360 ms 1272 KB Output is correct
5 Correct 749 ms 1624 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 33 ms 344 KB Output is correct
3 Correct 109 ms 856 KB Output is correct
4 Correct 348 ms 1212 KB Output is correct
5 Correct 706 ms 2548 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 117 ms 600 KB Output is correct
9 Correct 254 ms 856 KB Output is correct
10 Correct 722 ms 1572 KB Output is correct
11 Correct 722 ms 2592 KB Output is correct
12 Correct 702 ms 2028 KB Output is correct
13 Correct 719 ms 1896 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Correct 41 ms 344 KB Output is correct
17 Correct 66 ms 344 KB Output is correct
18 Correct 125 ms 856 KB Output is correct
19 Correct 263 ms 1224 KB Output is correct
20 Correct 245 ms 1412 KB Output is correct
21 Correct 747 ms 2636 KB Output is correct
22 Correct 684 ms 1904 KB Output is correct
23 Correct 681 ms 2400 KB Output is correct
24 Correct 653 ms 1848 KB Output is correct
25 Correct 10 ms 596 KB Output is correct
26 Correct 7 ms 344 KB Output is correct
27 Correct 23 ms 344 KB Output is correct
28 Correct 20 ms 344 KB Output is correct
29 Correct 27 ms 344 KB Output is correct
30 Correct 138 ms 712 KB Output is correct
31 Correct 160 ms 708 KB Output is correct
32 Correct 152 ms 1216 KB Output is correct
33 Correct 243 ms 1000 KB Output is correct
34 Correct 229 ms 1184 KB Output is correct
35 Correct 243 ms 1624 KB Output is correct
36 Correct 711 ms 1360 KB Output is correct
37 Correct 670 ms 1668 KB Output is correct
38 Correct 658 ms 1460 KB Output is correct
39 Correct 695 ms 2248 KB Output is correct
40 Correct 694 ms 1672 KB Output is correct
41 Correct 668 ms 1580 KB Output is correct
42 Correct 768 ms 1628 KB Output is correct
43 Correct 697 ms 2476 KB Output is correct
44 Correct 714 ms 2204 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 22 ms 596 KB Output is correct
48 Correct 19 ms 344 KB Output is correct
49 Correct 21 ms 344 KB Output is correct
50 Correct 157 ms 960 KB Output is correct
51 Correct 157 ms 956 KB Output is correct
52 Correct 153 ms 956 KB Output is correct
53 Correct 225 ms 856 KB Output is correct
54 Correct 238 ms 992 KB Output is correct
55 Correct 223 ms 788 KB Output is correct
56 Correct 663 ms 1304 KB Output is correct
57 Correct 665 ms 1772 KB Output is correct
58 Correct 696 ms 1932 KB Output is correct
59 Correct 677 ms 1956 KB Output is correct
60 Correct 663 ms 1952 KB Output is correct
61 Correct 692 ms 1368 KB Output is correct
62 Correct 656 ms 1052 KB Output is correct
63 Correct 863 ms 1856 KB Output is correct
64 Correct 666 ms 1672 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 22 ms 600 KB Output is correct
3 Partially correct 144 ms 1120 KB Output is partially correct
4 Partially correct 395 ms 1364 KB Output is partially correct
5 Partially correct 747 ms 2312 KB Output is partially correct
6 Incorrect 1 ms 500 KB Incorrect
7 Halted 0 ms 0 KB -