oj.uz

Submission #960338

# Submission time Handle Problem Language Result Execution time Memory
960338 2024-04-10T09:27:42 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 819 ms 1880 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++) {
        assert((int)tree[i].size() <= 2);
        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);
    if (p[pos] != -1) assert(find(adj[p[pos]].begin(), adj[p[pos]].end(), u) != adj[p[pos]].end());
    auto g = find(x.begin(), x.end(), pos);
    x.erase(g);
    g = find(x.begin(), x.end(), u); g++;
    x.insert(g, pos);
    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;   
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:88:14: warning: variable 'u' set but not used [-Wunused-but-set-variable]
   88 |         auto u = find(adj[x[i]].begin(), adj[x[i]].end(), x[i - 1]);
      |              ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 172 ms 1620 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Correct 121 ms 708 KB Output is correct
4 Correct 376 ms 1216 KB Output is correct
5 Correct 759 ms 1136 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 28 ms 344 KB Output is correct
3 Correct 137 ms 856 KB Output is correct
4 Correct 339 ms 1244 KB Output is correct
5 Correct 742 ms 1808 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Correct 132 ms 600 KB Output is correct
9 Correct 273 ms 888 KB Output is correct
10 Correct 727 ms 1880 KB Output is correct
11 Correct 781 ms 1404 KB Output is correct
12 Correct 772 ms 1572 KB Output is correct
13 Correct 690 ms 1272 KB Output is correct

Subtask #3
0.0 / 25.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 Correct 122 ms 976 KB Output is correct
4 Correct 351 ms 864 KB Output is correct
5 Correct 770 ms 1604 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 116 ms 600 KB Output is correct
9 Correct 329 ms 620 KB Output is correct
10 Correct 762 ms 1428 KB Output is correct
11 Correct 722 ms 1768 KB Output is correct
12 Correct 786 ms 1628 KB Output is correct
13 Correct 759 ms 1340 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 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 23 ms 344 KB Output is correct
3 Partially correct 116 ms 856 KB Output is partially correct
4 Partially correct 365 ms 1368 KB Output is partially correct
5 Partially correct 819 ms 1868 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Partially correct 126 ms 856 KB Output is partially correct
9 Partially correct 273 ms 1124 KB Output is partially correct
10 Partially correct 741 ms 1588 KB Output is partially correct
11 Partially correct 695 ms 1244 KB Output is partially correct
12 Partially correct 709 ms 1392 KB Output is partially correct
13 Partially correct 751 ms 1360 KB Output is partially correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -