oj.uz

Submission #1082447

# Submission time Handle Problem Language Result Execution time Memory
1082447 2024-08-31T11:07:20 Z Boas Longest Trip (IOI23_longesttrip) C++17
40 / 100
 923 ms 1288 KB 
#include "longesttrip.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T1, typename T2>
using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_set = indexed_map<T, null_type>;

#define loop(x, i) for (int i = 0; i < (x); i++)
#define loop1(x, i) for (int i = 1; i <= (x); i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define itloop(x) for (auto it = begin(x); x != end(x); it++)
#define itrev(x) for (auto it = rbegin(x); x != rend(x); it++)
#define INF32 ((int32_t)(2e9 + 1))
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define removeIn(x, l) l.erase(find(ALL(l), x))
#define pb push_back
#define sz(x) (int)(x).size()
#define F first
#define S second
#define var const auto &
#define foreach(l) for (var e : l)

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
typedef vector<si> vsi;
typedef vector<sii> vsii;
typedef vector<vsi> vvsi;
typedef vector<string> vstr;
typedef vector<vector<string>> vvstr;
typedef vector<bool> vb;
typedef vector<vb> vvb;

vi longest_trip(int N, int D)
{
    if (D >= 2)
    {
        vi res(N);
        iota(ALL(res), 0);
        if (D == 3)
        {
            return res;
        }
        si resterend;
        loop1(N - 1, i) resterend.insert(res[i]);
        loop1(N - 1, i)
        {
            auto it = resterend.begin();
            if (are_connected({res[i - 1]}, {*it}))
            {
                res[i] = *it;
                resterend.erase(it);
            }
            else
            {
                if (resterend.size() == 1)
                {
                    res.insert(res.begin(), *it);
                    res.pop_back();
                    return res;
                }
                res[i] = *next(it);
                resterend.erase(next(it));
            }
        }
        return res;
    }
    else
    {
        vvi adj(N);
        bitset<256> con[256];
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                if (are_connected({i}, {j}))
                {
                    // cerr << i << ' ' << j << endl;
                    adj[i].pb(j);
                    adj[j].pb(i);
                    con[i][j] = 1;
                    con[j][i] = 1;
                }
            }
        }
        vb vis(N);
        int cnt = 0;
        auto dfs = [&](auto &&self, int i) -> void
        {
            vis[i] = 1;
            cnt++;
            for (int j : adj[i])
            {
                if (!vis[j])
                    self(self, j);
            }
        };
        dfs(dfs, 0);
        vi res;
        if (cnt != N)
        {
            loop(N, i)
            {
                if (vis[i] == (cnt >= N / 2))
                    res.pb(i);
            }
            // loop(sz(res) - 1, i) assert(adj[res[i]].count(res[i + 1]));
            return res;
        }
        deque<int> path;
        path.pb(0);
        int i2 = *adj[0].begin();
        path.pb(i2);
        int i3 = -1;
        for (int j : adj[i2])
        {
            if (j != 0)
            {
                i3 = j;
                path.pb(i3);
                break;
            }
        }
        if (i3 == -1)
        {
            for (int j : adj[0])
            {
                if (j != i2)
                {
                    i3 = j;
                    path.push_front(i3);
                    break;
                }
            }
        }
        deque<int> left;
        for (int i = 1; i < N; i++)
            if (i != i2 && i != i3)
                left.pb(i);
        while (!left.empty())
        {
            int i = left.back();
            left.pop_back();
            if (con[i][path[0]])
            {
                path.push_front(i);
            }
            else if (con[i][path.back()])
            {
                path.push_back(i);
            }
            else
            {
                // assert(adj[path[0]].count(path.back()));
                int newBegin = -1;
                for (int j = 1; j < sz(path) - 1; j++)
                {
                    if (con[i][path[j]])
                    {
                        newBegin = j;
                        break;
                    }
                }
                if (newBegin == -1)
                {
                    left.push_front(i);
                    continue;
                }
                deque<int> newPath;
                newPath.pb(i);
                for (int j = newBegin; j < sz(path); j++)
                {
                    newPath.pb(path[j]);
                }
                for (int j = 0; j < newBegin; j++)
                {
                    newPath.pb(path[j]);
                }
                path = newPath;
            }
        }
        for (int v : path)
            res.pb(v);
        assert(sz(res) == N);
        // loop(sz(res) - 1, i) assert(adj[res[i]].count(res[i + 1]));
        return res;
    }
    throw;
    return {};
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# 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 0 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 7 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 440 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 7 ms 344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 146 ms 452 KB Output is correct
4 Correct 446 ms 856 KB Output is correct
5 Correct 822 ms 1228 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 145 ms 592 KB Output is correct
9 Correct 318 ms 504 KB Output is correct
10 Correct 869 ms 1016 KB Output is correct
11 Correct 836 ms 1232 KB Output is correct
12 Correct 909 ms 1132 KB Output is correct
13 Correct 845 ms 1128 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 600 KB Output is correct
16 Correct 48 ms 344 KB Output is correct
17 Correct 91 ms 340 KB Output is correct
18 Correct 160 ms 852 KB Output is correct
19 Correct 361 ms 860 KB Output is correct
20 Correct 292 ms 500 KB Output is correct
21 Correct 821 ms 1236 KB Output is correct
22 Correct 831 ms 900 KB Output is correct
23 Correct 859 ms 1044 KB Output is correct
24 Correct 874 ms 1008 KB Output is correct
25 Correct 10 ms 344 KB Output is correct
26 Correct 9 ms 344 KB Output is correct
27 Correct 34 ms 340 KB Output is correct
28 Correct 21 ms 344 KB Output is correct
29 Correct 23 ms 344 KB Output is correct
30 Correct 203 ms 344 KB Output is correct
31 Correct 180 ms 440 KB Output is correct
32 Correct 189 ms 344 KB Output is correct
33 Correct 311 ms 972 KB Output is correct
34 Correct 350 ms 988 KB Output is correct
35 Correct 306 ms 600 KB Output is correct
36 Correct 871 ms 972 KB Output is correct
37 Correct 849 ms 852 KB Output is correct
38 Correct 883 ms 940 KB Output is correct
39 Correct 869 ms 1092 KB Output is correct
40 Correct 897 ms 980 KB Output is correct
41 Correct 814 ms 1272 KB Output is correct
42 Correct 847 ms 712 KB Output is correct
43 Correct 813 ms 1040 KB Output is correct
44 Correct 832 ms 720 KB Output is correct
45 Correct 12 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 25 ms 344 KB Output is correct
48 Correct 25 ms 344 KB Output is correct
49 Correct 18 ms 344 KB Output is correct
50 Correct 207 ms 448 KB Output is correct
51 Correct 216 ms 592 KB Output is correct
52 Correct 216 ms 592 KB Output is correct
53 Correct 314 ms 848 KB Output is correct
54 Correct 315 ms 592 KB Output is correct
55 Correct 298 ms 728 KB Output is correct
56 Correct 839 ms 1228 KB Output is correct
57 Correct 839 ms 972 KB Output is correct
58 Correct 804 ms 1096 KB Output is correct
59 Correct 883 ms 1092 KB Output is correct
60 Correct 861 ms 708 KB Output is correct
61 Correct 873 ms 856 KB Output is correct
62 Correct 867 ms 1088 KB Output is correct
63 Correct 824 ms 1288 KB Output is correct
64 Correct 913 ms 1212 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Partially correct 174 ms 340 KB Output is partially correct
4 Partially correct 419 ms 1004 KB Output is partially correct
5 Partially correct 832 ms 888 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 19 ms 340 KB Output is correct
8 Partially correct 155 ms 592 KB Output is partially correct
9 Partially correct 320 ms 592 KB Output is partially correct
10 Partially correct 871 ms 952 KB Output is partially correct
11 Partially correct 876 ms 1184 KB Output is partially correct
12 Partially correct 853 ms 1096 KB Output is partially correct
13 Partially correct 923 ms 1184 KB Output is partially correct
14 Incorrect 1 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -