oj.uz

Submission #1081159

# Submission time Handle Problem Language Result Execution time Memory
1081159 2024-08-29T18:55:02 Z Macker Longest Trip (IOI23_longesttrip) C++17
60 / 100
 915 ms 728 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;

#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) (*s.begin())


vector<int> longest_trip(int n, int D)
{
    bool adj[256][256];
    FOR(i, n) FOR(j, n) adj[i][j] = 0;
    FOR(i, n) FOR(j, i) {
        if(are_connected({i}, {j})){
            adj[i][j] = 1;
            adj[j][i] = 1;
        }
    }

    { // 2 components
        vector<int> vis(n);
        vector<vector<int>> comp;
        function<void(int)> dfs = [&](int a){
            comp.back().push_back(a);
            vis[a] = 1;
            FOR(b, n) if(adj[a][b] && !vis[b]) dfs(b);    
        };

        FOR(i, n){
            if(!vis[i]) {
                comp.push_back({});
                dfs(i);
            }
        }

        if(comp.size() == 2){
            if(comp[0].size() < comp[1].size()) swap(comp[0], comp[1]);
            return comp[0];
        }
    }

    { // full graph
        bool full = 1;
        FOR(i, n) if(accumulate(adj[i], adj[i] + n, 0) != n - 1) full = 0;
        if(full) {
            vector<int> r;
            FOR(i, n) r.push_back(i);
            return r;
        }
    }

    bool vis[256];
    FOR(i, 256) vis[i] = 0;
    FOR(st, n){
        int a = -1, b;
        FOR(j, n) FOR(k, j){
            if(adj[st][j] && adj[st][k] && !adj[j][k]) a = j, b = k;
        }
        if(a == -1) continue;
        deque<int> res;
        res.push_back(st);
        res.push_back(a);
        res.push_front(b);
        vis[st] = 1; vis[a] = 1; vis[b] = 1;

        FOR(_, n){
            bool f = 0;
            FOR(j, n){
                if(vis[j]) continue;
                if(adj[a][j] && !adj[b][j]){
                    f = 1;
                    a = j;
                    res.push_back(a);
                    vis[a] = 1;
                }
                else if(adj[b][j] && !adj[a][j]){
                    f = 1;
                    b = j;
                    res.push_front(b);
                    vis[b] = 1;
                }
            }
            if(!f){
                f = 0;
                FOR(x, n){
                    if(vis[x]) continue;
                    FOR(y, x){
                        if(vis[y]) continue;
                        if(adj[a][x] && adj[b][y] && !adj[x][y]){
                            f = 1;
                            a = x;
                            b = y;
                            res.push_back(a);
                            vis[a] = 1;
                            res.push_front(b);
                            vis[b] = 1;
                        }
                    }
                }
                if(!f){
                    FOR(x, n) if(!vis[x]) res.push_back(x);
                    return vector<int>(all(res));
                }
            }
        }
        return vector<int>(all(res));
    }
    return {0};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 219 ms 472 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 22 ms 344 KB Output is correct
3 Correct 147 ms 344 KB Output is correct
4 Correct 421 ms 344 KB Output is correct
5 Correct 810 ms 476 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 28 ms 344 KB Output is correct
3 Correct 150 ms 344 KB Output is correct
4 Correct 403 ms 592 KB Output is correct
5 Correct 834 ms 472 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Correct 153 ms 344 KB Output is correct
9 Correct 312 ms 472 KB Output is correct
10 Correct 821 ms 472 KB Output is correct
11 Correct 811 ms 468 KB Output is correct
12 Correct 769 ms 472 KB Output is correct
13 Correct 840 ms 596 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 144 ms 344 KB Output is correct
4 Correct 388 ms 488 KB Output is correct
5 Correct 792 ms 476 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Correct 150 ms 344 KB Output is correct
9 Correct 329 ms 472 KB Output is correct
10 Correct 843 ms 472 KB Output is correct
11 Correct 819 ms 476 KB Output is correct
12 Correct 826 ms 472 KB Output is correct
13 Correct 856 ms 472 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Correct 55 ms 344 KB Output is correct
17 Correct 93 ms 344 KB Output is correct
18 Correct 146 ms 344 KB Output is correct
19 Correct 336 ms 344 KB Output is correct
20 Correct 310 ms 344 KB Output is correct
21 Correct 858 ms 472 KB Output is correct
22 Correct 829 ms 476 KB Output is correct
23 Correct 881 ms 472 KB Output is correct
24 Correct 822 ms 476 KB Output is correct
25 Correct 7 ms 344 KB Output is correct
26 Correct 9 ms 344 KB Output is correct
27 Correct 24 ms 344 KB Output is correct
28 Correct 24 ms 344 KB Output is correct
29 Correct 16 ms 344 KB Output is correct
30 Correct 182 ms 340 KB Output is correct
31 Correct 193 ms 344 KB Output is correct
32 Correct 194 ms 344 KB Output is correct
33 Correct 292 ms 592 KB Output is correct
34 Correct 318 ms 468 KB Output is correct
35 Correct 329 ms 728 KB Output is correct
36 Correct 863 ms 476 KB Output is correct
37 Correct 837 ms 592 KB Output is correct
38 Correct 819 ms 472 KB Output is correct
39 Correct 855 ms 472 KB Output is correct
40 Correct 861 ms 480 KB Output is correct
41 Correct 866 ms 472 KB Output is correct
42 Correct 898 ms 476 KB Output is correct
43 Correct 824 ms 476 KB Output is correct
44 Correct 847 ms 472 KB Output is correct
45 Correct 14 ms 344 KB Output is correct
46 Correct 12 ms 344 KB Output is correct
47 Correct 25 ms 344 KB Output is correct
48 Correct 32 ms 344 KB Output is correct
49 Correct 25 ms 344 KB Output is correct
50 Correct 186 ms 468 KB Output is correct
51 Correct 171 ms 344 KB Output is correct
52 Correct 202 ms 344 KB Output is correct
53 Correct 317 ms 344 KB Output is correct
54 Correct 289 ms 480 KB Output is correct
55 Correct 338 ms 476 KB Output is correct
56 Correct 829 ms 476 KB Output is correct
57 Correct 910 ms 472 KB Output is correct
58 Correct 899 ms 472 KB Output is correct
59 Correct 811 ms 476 KB Output is correct
60 Correct 861 ms 472 KB Output is correct
61 Correct 870 ms 484 KB Output is correct
62 Correct 814 ms 728 KB Output is correct
63 Correct 843 ms 476 KB Output is correct
64 Correct 850 ms 476 KB Output is correct

Subtask #4
19.999999998 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Partially correct 130 ms 344 KB Output is partially correct
4 Partially correct 413 ms 592 KB Output is partially correct
5 Partially correct 868 ms 476 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Partially correct 148 ms 344 KB Output is partially correct
9 Partially correct 308 ms 468 KB Output is partially correct
10 Partially correct 795 ms 472 KB Output is partially correct
11 Partially correct 813 ms 476 KB Output is partially correct
12 Partially correct 891 ms 472 KB Output is partially correct
13 Partially correct 810 ms 476 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 48 ms 344 KB Output is correct
17 Partially correct 82 ms 344 KB Output is partially correct
18 Partially correct 146 ms 344 KB Output is partially correct
19 Partially correct 312 ms 592 KB Output is partially correct
20 Partially correct 295 ms 344 KB Output is partially correct
21 Correct 9 ms 344 KB Output is correct
22 Correct 10 ms 344 KB Output is correct
23 Correct 18 ms 344 KB Output is correct
24 Correct 22 ms 340 KB Output is correct
25 Correct 23 ms 344 KB Output is correct
26 Partially correct 198 ms 344 KB Output is partially correct
27 Partially correct 208 ms 344 KB Output is partially correct
28 Partially correct 184 ms 344 KB Output is partially correct
29 Partially correct 314 ms 492 KB Output is partially correct
30 Partially correct 295 ms 344 KB Output is partially correct
31 Partially correct 320 ms 480 KB Output is partially correct
32 Correct 10 ms 344 KB Output is correct
33 Correct 13 ms 344 KB Output is correct
34 Correct 19 ms 344 KB Output is correct
35 Correct 22 ms 344 KB Output is correct
36 Correct 15 ms 344 KB Output is correct
37 Partially correct 199 ms 344 KB Output is partially correct
38 Partially correct 204 ms 344 KB Output is partially correct
39 Partially correct 197 ms 344 KB Output is partially correct
40 Partially correct 314 ms 596 KB Output is partially correct
41 Partially correct 354 ms 344 KB Output is partially correct
42 Partially correct 330 ms 472 KB Output is partially correct
43 Partially correct 863 ms 592 KB Output is partially correct
44 Partially correct 838 ms 472 KB Output is partially correct
45 Partially correct 881 ms 472 KB Output is partially correct
46 Partially correct 877 ms 472 KB Output is partially correct
47 Partially correct 784 ms 472 KB Output is partially correct
48 Partially correct 842 ms 476 KB Output is partially correct
49 Partially correct 856 ms 472 KB Output is partially correct
50 Partially correct 874 ms 476 KB Output is partially correct
51 Partially correct 819 ms 472 KB Output is partially correct
52 Partially correct 812 ms 472 KB Output is partially correct
53 Partially correct 884 ms 472 KB Output is partially correct
54 Partially correct 839 ms 472 KB Output is partially correct
55 Partially correct 886 ms 592 KB Output is partially correct
56 Partially correct 915 ms 476 KB Output is partially correct
57 Partially correct 910 ms 472 KB Output is partially correct
58 Partially correct 798 ms 472 KB Output is partially correct
59 Partially correct 782 ms 476 KB Output is partially correct
60 Partially correct 835 ms 472 KB Output is partially correct
61 Partially correct 794 ms 472 KB Output is partially correct
62 Partially correct 852 ms 472 KB Output is partially correct
63 Partially correct 830 ms 476 KB Output is partially correct
64 Partially correct 896 ms 472 KB Output is partially correct
65 Partially correct 829 ms 476 KB Output is partially correct
66 Partially correct 907 ms 344 KB Output is partially correct
67 Partially correct 876 ms 476 KB Output is partially correct
68 Partially correct 901 ms 488 KB Output is partially correct
69 Partially correct 857 ms 476 KB Output is partially correct
70 Partially correct 800 ms 476 KB Output is partially correct
71 Partially correct 826 ms 472 KB Output is partially correct
72 Partially correct 839 ms 472 KB Output is partially correct
73 Partially correct 832 ms 480 KB Output is partially correct
74 Partially correct 857 ms 480 KB Output is partially correct
75 Partially correct 876 ms 344 KB Output is partially correct
76 Partially correct 831 ms 472 KB Output is partially correct
77 Partially correct 832 ms 472 KB Output is partially correct
78 Partially correct 831 ms 596 KB Output is partially correct
79 Partially correct 793 ms 476 KB Output is partially correct
80 Partially correct 874 ms 728 KB Output is partially correct
81 Partially correct 823 ms 484 KB Output is partially correct
82 Partially correct 853 ms 480 KB Output is partially correct