oj.uz

Submission #980169

# Submission time Handle Problem Language Result Execution time Memory
980169 2024-05-12T00:31:58 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 803 ms 2556 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using dll = deque <ll>;
using vi = vector <int>;

const ll MAXN = 256+16;
vll adj[MAXN];
bool mat[MAXN][MAXN];
ll comp[MAXN];

void dfs (ll u, ll col, ll &sz) {
    if (comp[u]) return;
    comp[u] = col;
    sz++;
    for (ll v : adj[u]) {
        dfs(v, col, sz);
    }
}

vi longest_trip (int n, int d) {
    fill(adj, adj+n, vll({}));
    fill(comp, comp+n, 0);
    for (ll u = 0; u < n; u++) {
        mat[u][u] = false;
        for (ll v = u+1; v < n; v++) {
            if (are_connected(vi({ int(u) }), vi({ int(v) }))) {
                adj[u].push_back(v);
                adj[v].push_back(u);
                mat[u][v] = true;
                mat[v][u] = true;
            } else {
                mat[u][v] = false;
                mat[v][u] = false;
            }
        }
    }
    ll c = 1;
    vll sz;
    for (ll u = 0; u < n; u++) {
        if (comp[u]) continue;
        sz.push_back(0);
        dfs(u, c++, sz.back());
    }
    if (c == 2) {
        dll dq;
        dq.push_back(0);
        vector <char> vis(n, false);
        vis[0] = true;
        for (ll v = 0; v < n; v++) {
            if (mat[0][v]) {
                vis[v] = true;
                dq.push_back(v);
                break;
            }
        }
        for (ll u = 0; u < n; u++) {
            if (vis[u]) continue;
            vis[u] = true;
            if (mat[u][dq.front()]) {
                dq.push_front(u);
            } else if (mat[u][dq.back()]) {
                dq.push_back(u);
            } else assert(false);
        }
        vi ans(dq.begin(), dq.end());
        return ans;
    } else if (c == 3) {
        ll maxC = max_element(sz.begin(), sz.end())-sz.begin() + 1;
        vi ans;
        for (ll u = 0; u < n; u++) {
            if (comp[u] == maxC) {
                if (ans.size() >= 1) assert(mat[ans.back()][u]);
                ans.push_back(u);
            }
        }
        return ans;
    } else assert(false);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 179 ms 2556 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 9 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 123 ms 1112 KB Output is correct
4 Correct 357 ms 1052 KB Output is correct
5 Correct 713 ms 2116 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 24 ms 344 KB Output is correct
3 Correct 135 ms 1112 KB Output is correct
4 Correct 328 ms 1528 KB Output is correct
5 Correct 709 ms 2476 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 132 ms 856 KB Output is correct
9 Correct 276 ms 1364 KB Output is correct
10 Correct 726 ms 2240 KB Output is correct
11 Correct 748 ms 1908 KB Output is correct
12 Correct 731 ms 2372 KB Output is correct
13 Correct 794 ms 1896 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 25 ms 344 KB Output is correct
3 Correct 127 ms 1124 KB Output is correct
4 Correct 322 ms 1140 KB Output is correct
5 Correct 753 ms 1720 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 121 ms 852 KB Output is correct
9 Correct 258 ms 1152 KB Output is correct
10 Correct 753 ms 1572 KB Output is correct
11 Correct 729 ms 1916 KB Output is correct
12 Correct 750 ms 1700 KB Output is correct
13 Correct 725 ms 1684 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Runtime error 2 ms 600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Partially correct 125 ms 600 KB Output is partially correct
4 Partially correct 333 ms 1444 KB Output is partially correct
5 Partially correct 740 ms 1936 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Partially correct 131 ms 856 KB Output is partially correct
9 Partially correct 268 ms 1800 KB Output is partially correct
10 Partially correct 732 ms 1908 KB Output is partially correct
11 Partially correct 792 ms 1944 KB Output is partially correct
12 Partially correct 803 ms 1208 KB Output is partially correct
13 Partially correct 719 ms 1912 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Runtime error 2 ms 600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -