oj.uz

Submission #960327

# Submission time Handle Problem Language Result Execution time Memory
960327 2024-04-10T09:20:29 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 740 ms 1864 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> adj[256], tree[256];
bool vis[256];
struct DSU {
    int p[256], sze[256];
    void init (int n) {
        for (int i = 0; i < n; i++) {
            p[i] = i; sze[i] = 1;
        }
    }
    int find (int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool merge (int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return 0;
        if (sze[a] > sze[b]) swap(a, b);
        sze[b] += sze[a]; p[a] = b;
        return 1;
    }
} cur;
vector <int> x;
int p[256];
void dfs (int pos) {
    vis[pos] = 1; x.push_back(pos);
    for (auto j : adj[pos]) {
        if (vis[j]) continue;
        tree[pos].push_back(j);
        p[j] = pos;
        dfs(j);
    }
}
int get (int x) {
    if (tree[x].empty()) return x;
    return get(tree[x][0]);
}
vector <int> longest_trip (int n, int d) {
    for (int i = 0; i < n; i++) adj[i].clear(), tree[i].clear();
    memset(p, -1, sizeof(p));
    cur.init(n);
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (are_connected({i}, {j})) {
                adj[i].push_back(j);
                adj[j].push_back(i);
                cur.merge(i, j);
            }
        }
    }
    bool flag = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            flag |= cur.merge(i, j);
        }
    }
    if (flag) {
        memset(vis, 0, sizeof(vis));
        vector <int> ret; 
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                x.clear(); dfs(i);
                if ((int)x.size() > (int)ret.size()) ret = x;
            }
        }
        return ret;
    }
    memset(vis, 0, sizeof(vis));
    x.clear(); dfs(0);
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if ((int)tree[i].size() == 2) {
            assert(pos == -1);
            pos = i;
        }
    }
    if (pos == -1) return x;
    int u = get(tree[pos][0]), v = get(tree[pos][1]);
    if (p[pos] != -1 && find(adj[p[pos]].begin(), adj[p[pos]].end(), u) == adj[p[pos]].end()) swap(u, v);
    auto g = find(x.begin(), x.end(), pos) - x.begin();
    x.erase(x.begin() + g);
    g = find(x.begin(), x.end(), u) - x.begin(); g++;
    x.insert(x.begin() + g, pos);
    //assert((int)x.size() == n);
    for (int i = 1; i < (int)x.size(); i++) {
        auto u = find(adj[x[i]].begin(), adj[x[i]].end(), x[i - 1]);
        assert(u != adj[x[i]].end());
    }
    return x;   
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 178 ms 1636 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 127 ms 1368 KB Output is correct
4 Correct 349 ms 948 KB Output is correct
5 Correct 698 ms 1236 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 129 ms 1116 KB Output is correct
4 Correct 335 ms 1112 KB Output is correct
5 Correct 698 ms 1864 KB Output is correct
6 Correct 8 ms 500 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Correct 126 ms 856 KB Output is correct
9 Correct 280 ms 740 KB Output is correct
10 Correct 694 ms 1320 KB Output is correct
11 Correct 704 ms 1120 KB Output is correct
12 Correct 740 ms 1140 KB Output is correct
13 Correct 722 ms 1312 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Correct 130 ms 1112 KB Output is correct
4 Correct 358 ms 964 KB Output is correct
5 Correct 711 ms 1228 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Correct 138 ms 1624 KB Output is correct
9 Correct 251 ms 864 KB Output is correct
10 Correct 684 ms 1124 KB Output is correct
11 Correct 714 ms 1264 KB Output is correct
12 Correct 687 ms 1140 KB Output is correct
13 Correct 706 ms 1112 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Runtime error 2 ms 600 KB Execution killed with signal 6
17 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 23 ms 552 KB Output is correct
3 Partially correct 124 ms 720 KB Output is partially correct
4 Partially correct 337 ms 996 KB Output is partially correct
5 Partially correct 716 ms 1092 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Partially correct 119 ms 600 KB Output is partially correct
9 Partially correct 255 ms 872 KB Output is partially correct
10 Partially correct 689 ms 1588 KB Output is partially correct
11 Partially correct 671 ms 1004 KB Output is partially correct
12 Partially correct 719 ms 1132 KB Output is partially correct
13 Partially correct 700 ms 1580 KB Output is partially correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Runtime error 3 ms 600 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -