답안 #1080899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080899	2024-08-29T15:49:50 Z	asdasdqwer	가장 긴 여행 (IOI23_longesttrip)	C++17	40 / 100	900 ms	1516 KB

longesttrip

#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());
    for (int i=0;i<N;i++) {
        shuffle(g[i].begin(), g[i].end(), rng);
    }

    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);
            if (uniform_int_distribution<int>(0, 7)(rng) == 0) shuffle(g[node].begin(), g[node].end(), rng);

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

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

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

    return lng;
}

Subtask #0

0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	221 ms	772 KB	Output is correct

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Correct	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	340 KB	Output is correct
2	Correct	28 ms	344 KB	Output is correct
3	Correct	158 ms	440 KB	Output is correct
4	Correct	403 ms	468 KB	Output is correct
5	Correct	808 ms	1224 KB	Output is correct
6	Correct	9 ms	344 KB	Output is correct
7	Correct	22 ms	344 KB	Output is correct
8	Correct	141 ms	456 KB	Output is correct
9	Correct	309 ms	504 KB	Output is correct
10	Correct	867 ms	1088 KB	Output is correct
11	Correct	900 ms	1100 KB	Output is correct
12	Correct	871 ms	728 KB	Output is correct
13	Correct	859 ms	752 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	344 KB	Output is correct
2	Correct	25 ms	344 KB	Output is correct
3	Correct	173 ms	440 KB	Output is correct
4	Correct	404 ms	592 KB	Output is correct
5	Correct	878 ms	1100 KB	Output is correct
6	Correct	11 ms	500 KB	Output is correct
7	Correct	23 ms	344 KB	Output is correct
8	Correct	141 ms	608 KB	Output is correct
9	Correct	284 ms	592 KB	Output is correct
10	Correct	879 ms	1040 KB	Output is correct
11	Correct	827 ms	1144 KB	Output is correct
12	Correct	844 ms	1140 KB	Output is correct
13	Correct	855 ms	776 KB	Output is correct
14	Correct	9 ms	344 KB	Output is correct
15	Correct	12 ms	344 KB	Output is correct
16	Correct	46 ms	344 KB	Output is correct
17	Correct	98 ms	440 KB	Output is correct
18	Correct	152 ms	344 KB	Output is correct
19	Correct	320 ms	624 KB	Output is correct
20	Correct	323 ms	720 KB	Output is correct
21	Correct	856 ms	1516 KB	Output is correct
22	Correct	859 ms	1356 KB	Output is correct
23	Correct	882 ms	880 KB	Output is correct
24	Correct	863 ms	848 KB	Output is correct
25	Correct	11 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	28 ms	344 KB	Output is correct
29	Correct	21 ms	344 KB	Output is correct
30	Correct	200 ms	344 KB	Output is correct
31	Correct	173 ms	344 KB	Output is correct
32	Correct	206 ms	444 KB	Output is correct
33	Correct	300 ms	344 KB	Output is correct
34	Correct	284 ms	488 KB	Output is correct
35	Correct	312 ms	848 KB	Output is correct
36	Correct	772 ms	788 KB	Output is correct
37	Correct	759 ms	872 KB	Output is correct
38	Correct	864 ms	948 KB	Output is correct
39	Correct	863 ms	1248 KB	Output is correct
40	Correct	877 ms	868 KB	Output is correct
41	Correct	851 ms	780 KB	Output is correct
42	Correct	826 ms	1064 KB	Output is correct
43	Correct	807 ms	1104 KB	Output is correct
44	Correct	829 ms	844 KB	Output is correct
45	Correct	10 ms	344 KB	Output is correct
46	Correct	15 ms	344 KB	Output is correct
47	Correct	21 ms	340 KB	Output is correct
48	Correct	27 ms	344 KB	Output is correct
49	Correct	24 ms	344 KB	Output is correct
50	Correct	188 ms	464 KB	Output is correct
51	Correct	185 ms	848 KB	Output is correct
52	Correct	220 ms	436 KB	Output is correct
53	Correct	307 ms	592 KB	Output is correct
54	Correct	302 ms	460 KB	Output is correct
55	Correct	295 ms	600 KB	Output is correct
56	Correct	859 ms	968 KB	Output is correct
57	Correct	879 ms	884 KB	Output is correct
58	Correct	841 ms	940 KB	Output is correct
59	Correct	836 ms	1132 KB	Output is correct
60	Correct	878 ms	992 KB	Output is correct
61	Correct	856 ms	992 KB	Output is correct
62	Correct	818 ms	1252 KB	Output is correct
63	Correct	872 ms	1300 KB	Output is correct
64	Correct	872 ms	1112 KB	Output is correct

Subtask #4

0.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	344 KB	Output is correct
2	Correct	27 ms	344 KB	Output is correct
3	Partially correct	158 ms	600 KB	Output is partially correct
4	Partially correct	443 ms	344 KB	Output is partially correct
5	Partially correct	846 ms	1104 KB	Output is partially correct
6	Correct	9 ms	344 KB	Output is correct
7	Correct	31 ms	344 KB	Output is correct
8	Partially correct	176 ms	856 KB	Output is partially correct
9	Partially correct	347 ms	600 KB	Output is partially correct
10	Partially correct	846 ms	868 KB	Output is partially correct
11	Partially correct	869 ms	864 KB	Output is partially correct
12	Partially correct	842 ms	1048 KB	Output is partially correct
13	Partially correct	818 ms	956 KB	Output is partially correct
14	Correct	8 ms	344 KB	Output is correct
15	Correct	12 ms	344 KB	Output is correct
16	Correct	42 ms	344 KB	Output is correct
17	Partially correct	101 ms	344 KB	Output is partially correct
18	Partially correct	149 ms	456 KB	Output is partially correct
19	Partially correct	309 ms	980 KB	Output is partially correct
20	Partially correct	315 ms	972 KB	Output is partially correct
21	Correct	14 ms	344 KB	Output is correct
22	Correct	13 ms	344 KB	Output is correct
23	Correct	26 ms	344 KB	Output is correct
24	Correct	24 ms	344 KB	Output is correct
25	Correct	24 ms	344 KB	Output is correct
26	Partially correct	183 ms	344 KB	Output is partially correct
27	Partially correct	216 ms	452 KB	Output is partially correct
28	Partially correct	180 ms	344 KB	Output is partially correct
29	Partially correct	297 ms	712 KB	Output is partially correct
30	Partially correct	308 ms	600 KB	Output is partially correct
31	Partially correct	309 ms	492 KB	Output is partially correct
32	Correct	8 ms	344 KB	Output is correct
33	Correct	10 ms	344 KB	Output is correct
34	Incorrect	6 ms	344 KB	Incorrect
35	Halted	0 ms	0 KB	-