oj.uz

Submission #960324

# Submission time Handle Problem Language Result Execution time Memory
960324 2024-04-10T09:19:33 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 778 ms 2080 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 0 ms 344 KB Output is correct
2 Correct 175 ms 1832 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 116 ms 600 KB Output is correct
4 Correct 345 ms 1148 KB Output is correct
5 Correct 778 ms 1368 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 28 ms 344 KB Output is correct
3 Correct 139 ms 1128 KB Output is correct
4 Correct 377 ms 908 KB Output is correct
5 Correct 771 ms 1844 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 122 ms 856 KB Output is correct
9 Correct 271 ms 860 KB Output is correct
10 Correct 723 ms 1544 KB Output is correct
11 Correct 733 ms 1524 KB Output is correct
12 Correct 709 ms 1112 KB Output is correct
13 Correct 692 ms 2080 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 135 ms 856 KB Output is correct
4 Correct 340 ms 1472 KB Output is correct
5 Correct 752 ms 1120 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Correct 122 ms 704 KB Output is correct
9 Correct 285 ms 1112 KB Output is correct
10 Correct 736 ms 1232 KB Output is correct
11 Correct 721 ms 1628 KB Output is correct
12 Correct 762 ms 1388 KB Output is correct
13 Correct 745 ms 1232 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Runtime error 3 ms 856 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 22 ms 344 KB Output is correct
3 Partially correct 122 ms 1116 KB Output is partially correct
4 Partially correct 343 ms 736 KB Output is partially correct
5 Partially correct 737 ms 1284 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Partially correct 125 ms 856 KB Output is partially correct
9 Partially correct 257 ms 1220 KB Output is partially correct
10 Partially correct 770 ms 1508 KB Output is partially correct
11 Partially correct 702 ms 1324 KB Output is partially correct
12 Partially correct 751 ms 1332 KB Output is partially correct
13 Partially correct 721 ms 1792 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Runtime error 2 ms 600 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -