oj.uz

Submission #1076306

# Submission time Handle Problem Language Result Execution time Memory
1076306 2024-08-26T12:46:09 Z c2zi6 Longest Trip (IOI23_longesttrip) C++17
5 / 100
 912 ms 1216 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "longesttrip.h"

bool commonedge(VI a, VI b) {
    return !are_connected(a, b);
}
bool commonedge(int u, int v) {
    return !are_connected({u}, {v});
}

int n;
VVI gp;
VVI gpmatrix;

int mex(VI a) {
    set<int> st;
    for (int x : a) st.insert(x);
    for (int i = 0; i < 2e9; i++) if (st.count(i) == 0) return i;
    return -1;
}

VI longest_trip(int N, int D) {
    /*if (D >= 2) {*/
    /*    int n = N;*/
    /*    VI group(n, -1);*/
    /*    int last = 0;*/
    /*    rep(u, n) if (group[u] == -1) {*/
    /*        group[u] = last;*/
    /*        rep(v, n) if (group[v] == -1) {*/
    /*            if (commonedge({u}, {v})) group[v] = last;*/
    /*        }*/
    /*        last++;*/
    /*    }*/
    /*    VVI comp(last);*/
    /*    rep(u, n) comp[group[u]].pb(u);*/
    /*    sort(all(comp), [&](const VI& a, const VI& b){return a.size() > b.size();});*/
    /*    int prev = -1;*/
    /*    VI ans;*/
    /*    rep(_, 3) {*/
    /*        rep(i, last) {*/
    /*            assert(comp[i].size() <= 2);*/
    /*            if (comp[i].size() && i != prev) {*/
    /*                ans.pb(comp[i].back());*/
    /*                comp[i].pop_back();*/
    /*                prev = i;*/
    /*            }*/
    /*        }*/
    /*    }*/
    /*    rep(i, last) assert(comp[i].size() == 0);*/
    /*    return ans;*/
    /*}*/
    n = N;
    gp = VVI(n);
    gpmatrix = VVI(n, VI(n));
    replr(u, 0, n-1) {
        replr(v, u+1, n-1) {
            if (commonedge(u, v)) {
                gp[u].pb(v);
                gp[v].pb(u);
                gpmatrix[u][v] = gpmatrix[v][u] = true;
                /*cout << "found edge " << u << " " << v << endl;*/
            }
        }
    }
    VI vis(n);
    VI group(n, -1);
    int l = 0;
    rep(u, n) {
        VI ret;
        for (int v : gp[u]) if (group[v] != -1) ret.pb(group[v]);
        group[u] = mex(ret);
        setmax(l, group[u]+1);
    }
    VVI comp(l);
    rep(u, n) comp[group[u]].pb(u);

    mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
    for (VI& a : comp) shuffle(all(a), rng);

    VI ans;

    int prev = -1;
    while (true) {
        bool ayo = false;
        for (VI& a : comp) {
            VI nw;
            for (int x : a) {
                if (prev != -1 && gpmatrix[x][prev]) {
                    nw.pb(x);
                    continue;
                }
                ans.pb(x);
                prev = x;
                ayo = true;
            }
            a = nw;
        }
        if (ayo == false) break;
    }
    return ans;

    /*vis = VI(l);*/
    /*for (VI vec : comp) {*/
    /*    for (int x : vec) cout << x << " ";*/
    /*    cout << endl;*/
    /*}*/

    return {-1488};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 29 ms 416 KB Output is correct
3 Correct 157 ms 452 KB Output is correct
4 Correct 400 ms 484 KB Output is correct
5 Correct 800 ms 956 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 35 ms 412 KB Output is correct
3 Correct 159 ms 600 KB Output is correct
4 Correct 434 ms 344 KB Output is correct
5 Correct 854 ms 1000 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 21 ms 412 KB Output is correct
3 Correct 174 ms 344 KB Output is correct
4 Correct 438 ms 484 KB Output is correct
5 Correct 858 ms 992 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 170 ms 344 KB Output is correct
9 Correct 326 ms 592 KB Output is correct
10 Correct 912 ms 1196 KB Output is correct
11 Correct 840 ms 1212 KB Output is correct
12 Correct 878 ms 1216 KB Output is correct
13 Correct 864 ms 964 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

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 416 KB Output is correct
3 Partially correct 140 ms 344 KB Output is partially correct
4 Partially correct 422 ms 592 KB Output is partially correct
5 Partially correct 861 ms 1088 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -