oj.uz

Submission #1080889

# Submission time Handle Problem Language Result Execution time Memory
1080889 2024-08-29T15:45:29 Z asdasdqwer Longest Trip (IOI23_longesttrip) C++17
40 / 100
 941 ms 1372 KB 
#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

std::vector<int> longest_trip(int N, int D) {
    vector<vector<int>> g(N);
    if (D == 3) {
        vector<int> v;
        for (int i=0;i<N;i++) {
            v.push_back(i);
        }
        return v;
    }

    for (int i=0;i<N;i++) {
        for (int j=i+1;j<N;j++) {
            if (are_connected({i}, {j})) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    int tries = 20;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> lng;
    for (int i=0;i<tries;i++) {
        vector<int> tmp;
        vector<bool> vis(N, false);
        function<void(int)> dfs=[&](int node) {
            vis[node] = true;
            tmp.push_back(node);

            vector<int> suf;
            for (int j=0;j<g[node].size();j++)suf.push_back(j);
            shuffle(suf.begin(), suf.end(), rng);

            for (int x:suf) {
                if (!vis[g[node][x]]) {
                    dfs(g[node][x]);
                    break;
                }
            }
        };

        dfs(uniform_int_distribution<int>(0, N-1)(rng));

        if (lng.size() < tmp.size()) {
            lng = tmp;
        }
    }

    return lng;
}

Compilation message

longesttrip.cpp: In lambda function:
longesttrip.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int j=0;j<g[node].size();j++)suf.push_back(j);
      |                          ~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 234 ms 924 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 344 KB Output is correct
2 Correct 30 ms 344 KB Output is correct
3 Correct 176 ms 600 KB Output is correct
4 Correct 396 ms 588 KB Output is correct
5 Correct 845 ms 1200 KB Output is correct
6 Correct 12 ms 344 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Correct 146 ms 600 KB Output is correct
9 Correct 346 ms 536 KB Output is correct
10 Correct 836 ms 1192 KB Output is correct
11 Correct 837 ms 1220 KB Output is correct
12 Correct 842 ms 1260 KB Output is correct
13 Correct 885 ms 1200 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 188 ms 692 KB Output is correct
4 Correct 435 ms 832 KB Output is correct
5 Correct 859 ms 992 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 175 ms 856 KB Output is correct
9 Correct 355 ms 592 KB Output is correct
10 Correct 865 ms 1372 KB Output is correct
11 Correct 915 ms 1000 KB Output is correct
12 Correct 931 ms 1304 KB Output is correct
13 Correct 889 ms 1000 KB Output is correct
14 Correct 11 ms 344 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 36 ms 344 KB Output is correct
17 Correct 109 ms 344 KB Output is correct
18 Correct 157 ms 344 KB Output is correct
19 Correct 331 ms 872 KB Output is correct
20 Correct 316 ms 592 KB Output is correct
21 Correct 911 ms 1008 KB Output is correct
22 Correct 898 ms 1164 KB Output is correct
23 Correct 875 ms 1196 KB Output is correct
24 Correct 883 ms 1136 KB Output is correct
25 Correct 12 ms 344 KB Output is correct
26 Correct 10 ms 344 KB Output is correct
27 Correct 28 ms 344 KB Output is correct
28 Correct 23 ms 344 KB Output is correct
29 Correct 23 ms 344 KB Output is correct
30 Correct 200 ms 472 KB Output is correct
31 Correct 212 ms 344 KB Output is correct
32 Correct 195 ms 704 KB Output is correct
33 Correct 333 ms 624 KB Output is correct
34 Correct 301 ms 552 KB Output is correct
35 Correct 339 ms 724 KB Output is correct
36 Correct 929 ms 1060 KB Output is correct
37 Correct 865 ms 956 KB Output is correct
38 Correct 941 ms 924 KB Output is correct
39 Correct 856 ms 1116 KB Output is correct
40 Correct 892 ms 836 KB Output is correct
41 Correct 870 ms 896 KB Output is correct
42 Correct 878 ms 896 KB Output is correct
43 Correct 867 ms 1304 KB Output is correct
44 Correct 821 ms 972 KB Output is correct
45 Correct 13 ms 344 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 27 ms 344 KB Output is correct
48 Correct 30 ms 344 KB Output is correct
49 Correct 28 ms 344 KB Output is correct
50 Correct 217 ms 676 KB Output is correct
51 Correct 199 ms 344 KB Output is correct
52 Correct 195 ms 452 KB Output is correct
53 Correct 285 ms 532 KB Output is correct
54 Correct 325 ms 528 KB Output is correct
55 Correct 385 ms 1104 KB Output is correct
56 Correct 880 ms 1072 KB Output is correct
57 Correct 731 ms 976 KB Output is correct
58 Correct 807 ms 968 KB Output is correct
59 Correct 828 ms 904 KB Output is correct
60 Correct 825 ms 1072 KB Output is correct
61 Correct 792 ms 1012 KB Output is correct
62 Correct 881 ms 980 KB Output is correct
63 Correct 861 ms 1088 KB Output is correct
64 Correct 780 ms 1096 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Partially correct 137 ms 472 KB Output is partially correct
4 Partially correct 386 ms 724 KB Output is partially correct
5 Partially correct 760 ms 988 KB Output is partially correct
6 Correct 12 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Partially correct 138 ms 464 KB Output is partially correct
9 Partially correct 277 ms 540 KB Output is partially correct
10 Partially correct 870 ms 1136 KB Output is partially correct
11 Partially correct 905 ms 1004 KB Output is partially correct
12 Partially correct 873 ms 1248 KB Output is partially correct
13 Partially correct 825 ms 1044 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Correct 51 ms 344 KB Output is correct
17 Partially correct 103 ms 344 KB Output is partially correct
18 Partially correct 159 ms 676 KB Output is partially correct
19 Partially correct 317 ms 608 KB Output is partially correct
20 Partially correct 344 ms 740 KB Output is partially correct
21 Correct 14 ms 344 KB Output is correct
22 Correct 11 ms 344 KB Output is correct
23 Correct 38 ms 344 KB Output is correct
24 Correct 30 ms 344 KB Output is correct
25 Correct 31 ms 344 KB Output is correct
26 Partially correct 216 ms 468 KB Output is partially correct
27 Partially correct 184 ms 340 KB Output is partially correct
28 Partially correct 190 ms 692 KB Output is partially correct
29 Partially correct 306 ms 592 KB Output is partially correct
30 Partially correct 301 ms 544 KB Output is partially correct
31 Partially correct 342 ms 728 KB Output is partially correct
32 Correct 18 ms 344 KB Output is correct
33 Correct 17 ms 344 KB Output is correct
34 Incorrect 10 ms 344 KB Incorrect
35 Halted 0 ms 0 KB -