oj.uz

Submission #944628

# Submission time Handle Problem Language Result Execution time Memory
944628 2024-03-13T02:09:09 Z Nhoksocqt1 Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 600 KB 
#ifndef Nhoksocqt1
    #include "longesttrip.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 260;

#ifdef Nhoksocqt1

bitset<MAXN> adjp[MAXN], idA, idB, bsA, bsB;
struct Jury {
    int n, d;

    void init(int _n, int _d) {
        n = _n, d = _d;
        int u, v;
        bool check(0);
        while(cin >> u >> v) {
            adjp[u][v] = adjp[v][u] = 1;
            check = 1;
        }

        if(!check) {
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    for (int k = j + 1; k < n; ++k) {
                        int cnt = adjp[i][j] + adjp[i][k] + adjp[j][k];
                        if(cnt < d) {
                            vector<ii> p;
                            p.push_back(ii(i, j));
                            p.push_back(ii(i, k));
                            p.push_back(ii(j, k));

                            while(cnt < d) {
                                int r = Random(0, 2);
                                if(adjp[p[r].fi][p[r].se])
                                    continue;

                                ++cnt;
                                adjp[p[r].fi][p[r].se] = adjp[p[r].se][p[r].fi] = 1;
                                cout << p[r].fi << ' ' << p[r].se << '\n';
                            }
                        }
                    }
                }
            }
        }
    }

    bool are_connected(vector<int> &A, vector<int> &B) {
        bsA = bsB = idA = idB = 0;
        for (int it = 0; it < sz(A); ++it) {
            bsA |= adjp[A[it]];
            idA[A[it]] = 1;
        }

        for (int it = 0; it < sz(B); ++it) {
            bsB |= adjp[B[it]];
            idB[B[it]] = 1;
        }

        return ((bsA & idB).count() > 0 || (bsB & idA).count() > 0);
    }

} jury;

#endif // Nhoksocqt1

vector<int> A[MAXN];
int nxt[MAXN], numNode;
bool adj[MAXN][MAXN], dx[MAXN];

bool check_are_connected(vector<int> &A, vector<int> &B) {
    #ifdef Nhoksocqt1
        return jury.are_connected(A, B);
    #else
        return are_connected(A, B);
    #endif // Nhoksocqt1
}

int evaluation(int u, int lenNow, int pNxt[]) {
    int nxt[numNode + 1];
    for (int i = 0; i <= numNode; ++i)
        nxt[i] = pNxt[i];

    vector<int> tmp;
    while(1) {
        dx[u] = 1;
        tmp.push_back(u);

        ++lenNow;
        int v(-1), prv(-1);
        for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
            if(!dx[i] && adj[u][i]) {
                v = i, prv = j;
                break;
            }
        }

        if(v < 0)
            break;

        nxt[prv] = nxt[v];
        u = v;
    }

    while(sz(tmp)) {
        dx[tmp.back()] = 0;
        tmp.pop_back();
    }

    return lenNow;
}

int evaluation2(int u, int lenNow, int pNxt[], vector<int> &ans, bool trace) {
    int nxt[numNode + 1];
    for (int i = 0; i <= numNode; ++i)
        nxt[i] = pNxt[i];

    vector<int> tmp;
    while(1) {
        dx[u] = 1;
        tmp.push_back(u);

        ++lenNow;
        int maxLen(0), v(-1), prv(-1);
        for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
            if(!dx[i] && adj[u][i]) {
                int len = evaluation(i, lenNow, nxt);
                if(len == numNode) {
                    maxLen = len;
                    v = i, prv = j;
                }
            }
        }

        if(v < 0)
            break;

        nxt[prv] = nxt[v];
        u = v;
    }

    if(trace)
        ans = tmp;

    while(sz(tmp)) {
        dx[tmp.back()] = 0;
        tmp.pop_back();
    }

    return lenNow;
}

vector<int> longest_trip(int N, int D) {
    numNode = N;
    if(D == 3) {
        vector<int> ans;
        for (int i = 0; i < numNode; ++i)
            ans.push_back(i);

        return ans;
    }

    for (int u = 0; u < numNode; ++u) {
        for (int v = u + 1; v < numNode; ++v) {
            vector<int> A, B;
            A.push_back(u);
            B.push_back(v);
            adj[u][v] = adj[v][u] = check_are_connected(A, B);
        }
    }

    nxt[numNode] = 0;
    for (int i = 0; i < numNode; ++i) {
        dx[i] = 0;
        nxt[i] = i + 1;
    }

    vector<int> ans;
    int len(0), u(-1), prv(-1);
    for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
        int len = evaluation2(i, 0, nxt, ans, 0);
        if(len == numNode) {
            evaluation2(i, 0, nxt, ans, 1);
            break;
        }
    }

    return ans;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "longesttrip"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int n, d;
    cin >> n >> d;
    jury.init(n, d);

    vector<int> path = longest_trip(n, d);
    cout << "ANSWER: " << sz(path) << ": ";
    for (int it = 0; it < sz(path); ++it)
        cout << path[it] << ' '; cout << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message

longesttrip.cpp: In function 'int evaluation2(int, int, int*, std::vector<int>&, bool)':
longesttrip.cpp:139:13: warning: variable 'maxLen' set but not used [-Wunused-but-set-variable]
  139 |         int maxLen(0), v(-1), prv(-1);
      |             ^~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:195:32: warning: variable 'j' set but not used [-Wunused-but-set-variable]
  195 |     for (int i = nxt[numNode], j = numNode; i < numNode; j = i, i = nxt[i]) {
      |                                ^
longesttrip.cpp:194:9: warning: unused variable 'len' [-Wunused-variable]
  194 |     int len(0), u(-1), prv(-1);
      |         ^~~
longesttrip.cpp:194:17: warning: unused variable 'u' [-Wunused-variable]
  194 |     int len(0), u(-1), prv(-1);
      |                 ^
longesttrip.cpp:194:24: warning: unused variable 'prv' [-Wunused-variable]
  194 |     int len(0), u(-1), prv(-1);
      |                        ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 143 ms 344 KB Output is correct
4 Correct 448 ms 464 KB Output is correct
5 Execution timed out 1010 ms 496 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 135 ms 344 KB Output is correct
4 Correct 438 ms 460 KB Output is correct
5 Correct 976 ms 600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 141 ms 464 KB Output is correct
9 Correct 321 ms 344 KB Output is correct
10 Execution timed out 1020 ms 496 KB Time limit exceeded
11 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 27 ms 344 KB Output is correct
3 Partially correct 133 ms 344 KB Output is partially correct
4 Partially correct 443 ms 484 KB Output is partially correct
5 Execution timed out 1014 ms 492 KB Time limit exceeded
6 Halted 0 ms 0 KB -