oj.uz

Submission #980174

# Submission time Handle Problem Language Result Execution time Memory
980174 2024-05-12T00:35:24 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 785 ms 2412 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+5, 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) {
                ans.push_back(u);
            }
        }
        return ans;
    }
}

Compilation message

longesttrip.cpp: In function 'vi longest_trip(int, int)':
longesttrip.cpp:41:9: warning: control reaches end of non-void function [-Wreturn-type]
   41 |     vll sz;
      |         ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 180 ms 1868 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 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 123 ms 856 KB Output is correct
4 Correct 384 ms 1164 KB Output is correct
5 Correct 737 ms 1628 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 26 ms 600 KB Output is correct
3 Correct 125 ms 1244 KB Output is correct
4 Correct 367 ms 1368 KB Output is correct
5 Correct 724 ms 1612 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 125 ms 612 KB Output is correct
9 Correct 256 ms 1124 KB Output is correct
10 Correct 741 ms 1940 KB Output is correct
11 Correct 710 ms 1928 KB Output is correct
12 Correct 766 ms 1660 KB Output is correct
13 Correct 719 ms 2036 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 21 ms 344 KB Output is correct
3 Correct 144 ms 600 KB Output is correct
4 Correct 366 ms 1528 KB Output is correct
5 Correct 735 ms 2016 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 125 ms 872 KB Output is correct
9 Correct 291 ms 1028 KB Output is correct
10 Correct 754 ms 2352 KB Output is correct
11 Correct 734 ms 2412 KB Output is correct
12 Correct 744 ms 2220 KB Output is correct
13 Correct 785 ms 2196 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 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 138 ms 620 KB Output is partially correct
4 Partially correct 366 ms 1136 KB Output is partially correct
5 Partially correct 724 ms 1876 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Partially correct 128 ms 600 KB Output is partially correct
9 Partially correct 296 ms 1368 KB Output is partially correct
10 Partially correct 724 ms 1648 KB Output is partially correct
11 Partially correct 751 ms 2048 KB Output is partially correct
12 Partially correct 729 ms 1524 KB Output is partially correct
13 Partially correct 740 ms 1884 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Runtime error 2 ms 604 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -