oj.uz

Submission #1076208

# Submission time Handle Problem Language Result Execution time Memory
1076208 2024-08-26T11:47:07 Z c2zi6 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 873 ms 600 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 samecomp(VI a, VI b) {
    return !are_connected(a, b);
}

VI longest_trip(int N, int D) {
    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 (samecomp({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();});
    /*cout << "components" << endl;*/
    /*rep(i, last) {*/
    /*    for (int x : comp[i]) cout << x << " ";*/
    /*    cout << endl;*/
    /*}*/
    /*cout << "components" << endl;*/
    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;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 142 ms 344 KB Output is correct
4 Correct 407 ms 412 KB Output is correct
5 Correct 821 ms 412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 157 ms 344 KB Output is correct
4 Correct 420 ms 408 KB Output is correct
5 Correct 792 ms 412 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 91 ms 344 KB Output is correct
9 Correct 144 ms 344 KB Output is correct
10 Correct 465 ms 408 KB Output is correct
11 Correct 440 ms 412 KB Output is correct
12 Correct 433 ms 408 KB Output is correct
13 Correct 463 ms 416 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 148 ms 340 KB Output is correct
4 Correct 389 ms 344 KB Output is correct
5 Correct 850 ms 408 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 75 ms 344 KB Output is correct
9 Correct 161 ms 344 KB Output is correct
10 Correct 484 ms 412 KB Output is correct
11 Correct 422 ms 408 KB Output is correct
12 Correct 371 ms 416 KB Output is correct
13 Correct 421 ms 408 KB Output is correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Partially correct 151 ms 432 KB Output is partially correct
4 Partially correct 422 ms 416 KB Output is partially correct
5 Partially correct 873 ms 344 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Partially correct 78 ms 344 KB Output is partially correct
9 Partially correct 165 ms 344 KB Output is partially correct
10 Partially correct 477 ms 412 KB Output is partially correct
11 Partially correct 405 ms 416 KB Output is partially correct
12 Partially correct 455 ms 412 KB Output is partially correct
13 Partially correct 423 ms 428 KB Output is partially correct
14 Incorrect 1 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -