oj.uz

Submission #1082206

# Submission time Handle Problem Language Result Execution time Memory
1082206 2024-08-30T20:41:51 Z Boas Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 5936 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
    {
        vsi adj(N);
        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].insert(j);
                    adj[j].insert(i);
                }
            }
        }
        if (N <= 10)
        {
            vi best;
            for (int mask = 1; mask < (1 << N); mask++)
            {
                vi all;
                loop(N, i) if ((1 << i) & mask) all.pb(i);
                do
                {
                    if (sz(all) <= sz(best))
                        break;
                    bool val = 1;
                    loop(sz(all) - 1, i) if (!adj[all[i]].count(all[i + 1]))
                    {
                        val = 0;
                    }
                    if (val)
                        best = all;
                } while (next_permutation(ALL(all)));
            }
            if (sz(best) != N)
            {
                vb comp(N);
                for (int i : best)
                {
                    for (int j : best)
                    {
                        if (i != j && !adj[i].count(j))
                            throw;
                    }
                    comp[i] = 1;
                }
                vi others;
                loop(N, i) if (!comp[i]) others.pb(i);
                for (int i : others)
                {
                    for (int j : others)
                    {
                        if (i != j && !adj[i].count(j))
                            throw;
                    }
                }
            }
            return best;
        }
        si clique1, clique2;
        auto checkCliques = [&]()
        {
            for (int i : clique1)
            {
                for (int j : clique1)
                {
                    assert(i == j || adj[i].count(j));
                }
            }
            for (int i : clique2)
            {
                for (int j : clique2)
                {
                    assert(i == j || adj[i].count(j));
                }
            }
        };
        loop(2, iter) loop(N, i)
        {
            for (int j = i + 1; j < N; j++)
            {
                if (adj[i].count(j))
                    continue;
                if (clique1.empty())
                {
                    clique1.insert(i);
                    clique2.insert(j);
                }
                else
                {
                    bool iVal2 = 1, iVal1 = 1, jVal2 = 1, jVal1 = 1;
                    for (int k : clique1)
                    {
                        if (k != i && !adj[i].count(k))
                        {
                            iVal1 = 0;
                        }
                        if (k != j && !adj[j].count(k))
                        {
                            jVal1 = 0;
                        }
                    }
                    for (int k : clique2)
                    {
                        if (i != k && !adj[i].count(k))
                        {
                            iVal2 = 0;
                        }
                        if (j != k && !adj[j].count(k))
                        {
                            jVal2 = 0;
                        }
                    }
                    if (iVal1 && jVal2 && !iVal2 && !jVal1)
                    {
                        clique1.insert(i);
                        clique2.insert(j);
                    }
                    if (iVal2 && jVal1 && !iVal1 && !jVal2)
                    {
                        clique2.insert(i);
                        clique1.insert(j);
                    }
                }
            }
        }
        checkCliques();
        loop(N, i)
        {
            if (clique1.count(i) || clique2.count(i))
                continue;
            bool iVal2 = 1, iVal1 = 1;
            for (int k : clique1)
            {
                if (!adj[i].count(k))
                {
                    iVal1 = 0;
                }
            }
            for (int k : clique2)
            {
                if (!adj[i].count(k))
                {
                    iVal2 = 0;
                }
            }
            if (iVal1)
            {
                clique1.insert(i);
            }
            else if (iVal2)
            {
                clique2.insert(i);
            }
        }
        ii bridge = {-1, -1};
        for (int i : clique1)
        {
            for (int j : adj[i])
            {
                if (clique2.count(j))
                {
                    bridge = {i, j};
                    break;
                }
            }
        }
        assert(sz(clique1) + sz(clique2) == N);
        checkCliques();
        vi res;
        if (bridge.F == -1)
        {
            if (sz(clique1) < sz(clique2))
            {
                swap(clique1, clique2);
            }
            for (int i : clique1)
                res.pb(i);
            // loop(sz(res) - 1, i) assert(adj[res[i]].count(res[i + 1]));
            return res;
        }
        for (int i : clique1)
        {
            if (i != bridge.F)
                res.pb(i);
        }
        res.pb(bridge.F);
        res.pb(bridge.S);
        for (int i : clique2)
        {
            if (i != bridge.S)
                res.pb(i);
        }
        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 Runtime error 249 ms 5936 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 9 ms 340 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 42 ms 344 KB Output is correct
3 Correct 156 ms 712 KB Output is correct
4 Correct 424 ms 1316 KB Output is correct
5 Correct 969 ms 3424 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 82 ms 344 KB Output is correct
8 Correct 146 ms 340 KB Output is correct
9 Correct 345 ms 1108 KB Output is correct
10 Correct 955 ms 3564 KB Output is correct
11 Correct 915 ms 3832 KB Output is correct
12 Correct 882 ms 3960 KB Output is correct
13 Correct 941 ms 3708 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Runtime error 2 ms 600 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 48 ms 344 KB Output is correct
3 Partially correct 161 ms 344 KB Output is partially correct
4 Partially correct 459 ms 1100 KB Output is partially correct
5 Partially correct 913 ms 3388 KB Output is partially correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 83 ms 344 KB Output is correct
8 Partially correct 163 ms 480 KB Output is partially correct
9 Partially correct 348 ms 848 KB Output is partially correct
10 Partially correct 941 ms 3828 KB Output is partially correct
11 Execution timed out 1014 ms 4020 KB Time limit exceeded
12 Halted 0 ms 0 KB -