oj.uz

Submission #1046214

# Submission time Handle Problem Language Result Execution time Memory
1046214 2024-08-06T11:47:44 Z RecursiveCo Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 848 KB 
// CF template, version 3.0

#include <bits/stdc++.h>
#include "longesttrip.h"

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

vector<int> parent;

int find(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find(parent[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    parent[a] = b;
}

vector<int> longest_trip(int N, int _D) {
    vector<vector<bool>> adjMatrix(N, vector<bool>(N, false));
    vector<int> path;
    vector<int> other(N, true);
    forto(N, i) parent.push_back(i);
    forto(N, i) {
        vector<int> A;
        A.push_back(i);
        for (int j = i + 1; j < N; j++) {
            vector<int> B;
            B.push_back(j);
            bool edge = are_connected(A, B);
            if (edge) {
                unite(i, j);
                adjMatrix[i][j] = adjMatrix[j][i] = true;
                if (path.empty()) path.push_back(i), path.push_back(j), other[i] = other[j] = false;
            }
        }
    }
    bool connected = true;
    forto(N, i) if (find(i) != find(0)) connected = false;
    if (!connected) {
        vector<int> one;
        vector<int> two;
        forto(N, i) {
            if (find(i) == find(0)) one.push_back(i);
            else two.push_back(i);
        }
        if (one.size() > two.size()) swap(one, two);
        return two;
    }
    vector<int> newpath;
    while (path.size() < N) {
        int s = path.size();
        newpath.clear();
        if (adjMatrix[path[0]][path[s - 1]]) {
            forto(N, i) {
                if (!other[i]) continue;
                int j = 0;
                bool found = false;
                for (int p: path) {
                    if (adjMatrix[i][p]) {
                        other[i] = false;
                        found = true;
                        newpath.push_back(i);
                        for (int k = j; k < s; k++) newpath.push_back(path[k]);
                        forto(j, k) newpath.push_back(path[k]);
                        swap(path, newpath);
                        break;
                    }
                    j++;
                }
                if (found) break;
            }
        } else {
            forto(N, i) {
                if (!other[i]) continue;
                if (adjMatrix[i][path[0]]) {
                    rev(path);
                    path.push_back(i);
                    other[i] = false;
                    break;
                }
                if (adjMatrix[i][path[s - 1]]) {
                    path.push_back(i);
                    other[i] = false;
                    break;
                }
            }
        }
    }
    return path;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:89:5: note: in expansion of macro 'forto'
   89 |     forto(N, i) parent.push_back(i);
      |     ^~~~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:90:5: note: in expansion of macro 'forto'
   90 |     forto(N, i) {
      |     ^~~~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:105:5: note: in expansion of macro 'forto'
  105 |     forto(N, i) if (find(i) != find(0)) connected = false;
      |     ^~~~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:109:9: note: in expansion of macro 'forto'
  109 |         forto(N, i) {
      |         ^~~~~
longesttrip.cpp:117:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     while (path.size() < N) {
      |            ~~~~~~~~~~~~^~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:121:13: note: in expansion of macro 'forto'
  121 |             forto(N, i) {
      |             ^~~~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:131:25: note: in expansion of macro 'forto'
  131 |                         forto(j, k) newpath.push_back(path[k]);
      |                         ^~~~~
longesttrip.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
longesttrip.cpp:140:13: note: in expansion of macro 'forto'
  140 |             forto(N, i) {
      |             ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 21 ms 440 KB Output is correct
3 Correct 129 ms 416 KB Output is correct
4 Correct 327 ms 428 KB Output is correct
5 Correct 697 ms 456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 19 ms 440 KB Output is correct
3 Correct 135 ms 592 KB Output is correct
4 Correct 319 ms 428 KB Output is correct
5 Correct 677 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 119 ms 344 KB Output is correct
9 Correct 257 ms 344 KB Output is correct
10 Correct 705 ms 440 KB Output is correct
11 Correct 674 ms 440 KB Output is correct
12 Correct 745 ms 692 KB Output is correct
13 Correct 710 ms 440 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 16 ms 344 KB Output is correct
3 Correct 118 ms 344 KB Output is correct
4 Correct 363 ms 420 KB Output is correct
5 Correct 737 ms 448 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 17 ms 344 KB Output is correct
8 Correct 131 ms 416 KB Output is correct
9 Correct 247 ms 428 KB Output is correct
10 Correct 746 ms 592 KB Output is correct
11 Correct 696 ms 692 KB Output is correct
12 Correct 705 ms 444 KB Output is correct
13 Correct 700 ms 444 KB Output is correct
14 Execution timed out 3027 ms 344 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 21 ms 436 KB Output is correct
3 Partially correct 127 ms 344 KB Output is partially correct
4 Partially correct 314 ms 428 KB Output is partially correct
5 Partially correct 669 ms 448 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 15 ms 436 KB Output is correct
8 Partially correct 146 ms 344 KB Output is partially correct
9 Partially correct 298 ms 848 KB Output is partially correct
10 Partially correct 675 ms 440 KB Output is partially correct
11 Partially correct 715 ms 592 KB Output is partially correct
12 Partially correct 758 ms 436 KB Output is partially correct
13 Partially correct 711 ms 448 KB Output is partially correct
14 Execution timed out 3029 ms 344 KB Time limit exceeded
15 Halted 0 ms 0 KB -