oj.uz

Submission #980156

# Submission time Handle Problem Language Result Execution time Memory
980156 2024-05-12T00:22:39 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 792 ms 2472 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 {
                dq.push_back(u);
            }
        }
        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) {
                ans.push_back(u);
            }
        }
        return ans;
    } else assert(false);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 180 ms 2472 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 123 ms 856 KB Output is correct
4 Correct 370 ms 1112 KB Output is correct
5 Correct 772 ms 1412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 121 ms 600 KB Output is correct
4 Correct 365 ms 1368 KB Output is correct
5 Correct 727 ms 2260 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 121 ms 856 KB Output is correct
9 Correct 278 ms 1388 KB Output is correct
10 Correct 733 ms 1900 KB Output is correct
11 Correct 716 ms 2204 KB Output is correct
12 Correct 714 ms 1940 KB Output is correct
13 Correct 718 ms 1888 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 29 ms 344 KB Output is correct
3 Correct 154 ms 860 KB Output is correct
4 Correct 353 ms 1416 KB Output is correct
5 Correct 676 ms 2456 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 24 ms 540 KB Output is correct
8 Correct 115 ms 860 KB Output is correct
9 Correct 286 ms 1132 KB Output is correct
10 Correct 761 ms 2108 KB Output is correct
11 Correct 734 ms 1408 KB Output is correct
12 Correct 728 ms 1808 KB Output is correct
13 Correct 758 ms 1884 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 7 ms 344 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Partially correct 113 ms 600 KB Output is partially correct
4 Partially correct 362 ms 1368 KB Output is partially correct
5 Partially correct 723 ms 2052 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 121 ms 856 KB Output is partially correct
9 Partially correct 250 ms 1516 KB Output is partially correct
10 Partially correct 792 ms 1908 KB Output is partially correct
11 Partially correct 734 ms 1916 KB Output is partially correct
12 Partially correct 743 ms 1988 KB Output is partially correct
13 Partially correct 738 ms 1948 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Incorrect 2 ms 384 KB Incorrect
16 Halted 0 ms 0 KB -