oj.uz

Submission #980222

# Submission time Handle Problem Language Result Execution time Memory
980222 2024-05-12T01:20:42 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 926 ms 2492 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+5, 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());
    }
    assert(c == 2 || c == 3);
    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;
            }
        }
        assert(dq.size() == 2);
        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;
        for (ll i : dq) ans.push_back(i);
        return ans;
    } else if (c == 3) {
        assert(sz.size() == 2);
        if (sz[0] > sz[1]) {
            vi ans;
            for (ll u = 0; u < n; u++) {
                if (comp[u] == 1) {
                    ans.push_back(u);
                }
            }
            return ans;
        } else {
            vi ans;
            for (ll u = 0; u < n; u++) {
                if (comp[u] == 2) {
                    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 600 KB Output is correct
2 Runtime error 227 ms 2492 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 10 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 165 ms 1492 KB Output is correct
4 Correct 425 ms 1076 KB Output is correct
5 Correct 819 ms 2136 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 600 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 133 ms 1112 KB Output is correct
4 Correct 451 ms 1088 KB Output is correct
5 Correct 830 ms 2120 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 37 ms 600 KB Output is correct
8 Correct 135 ms 1248 KB Output is correct
9 Correct 334 ms 1264 KB Output is correct
10 Correct 844 ms 2344 KB Output is correct
11 Correct 866 ms 1700 KB Output is correct
12 Correct 854 ms 1824 KB Output is correct
13 Correct 737 ms 1980 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 516 KB Output is correct
2 Correct 30 ms 600 KB Output is correct
3 Correct 137 ms 736 KB Output is correct
4 Correct 398 ms 1076 KB Output is correct
5 Correct 738 ms 1228 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Correct 142 ms 856 KB Output is correct
9 Correct 356 ms 1272 KB Output is correct
10 Correct 873 ms 1712 KB Output is correct
11 Correct 856 ms 1588 KB Output is correct
12 Correct 759 ms 2028 KB Output is correct
13 Correct 818 ms 2176 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Runtime error 2 ms 856 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 25 ms 352 KB Output is correct
3 Partially correct 150 ms 980 KB Output is partially correct
4 Partially correct 418 ms 1076 KB Output is partially correct
5 Partially correct 880 ms 1664 KB Output is partially correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 30 ms 600 KB Output is correct
8 Partially correct 169 ms 1392 KB Output is partially correct
9 Partially correct 322 ms 1436 KB Output is partially correct
10 Partially correct 886 ms 1968 KB Output is partially correct
11 Partially correct 909 ms 1976 KB Output is partially correct
12 Partially correct 883 ms 1680 KB Output is partially correct
13 Partially correct 926 ms 1456 KB Output is partially correct
14 Correct 9 ms 344 KB Output is correct
15 Runtime error 3 ms 600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -