oj.uz

Submission #1050319

# Submission time Handle Problem Language Result Execution time Memory
1050319 2024-08-09T08:43:30 Z phoenix Longest Trip (IOI23_longesttrip) C++17
5 / 100
 691 ms 1248 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#define cerr if (false) cout
#endif

struct info {
    vector<int> A;
    vector<int> B;
    vector<int> ord;
};

int N;

bool g[256][256];

bool are_con(vector<int> a, vector<int> b) {
    return are_connected(a, b);
} 

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

vector<int> operator + (vector<int> a, vector<int> b) {
    for (int c : b) a.push_back(c);
    return a;
} 

void print(vector<int> a) {
    cerr << '{';
    for (int c : a) 
        cerr << c << ' ';
    cerr << '}';
    cerr << '\n';
}

vector<int> fin(vector<int> V, int x) {
    for (int i = 0; i < (int)V.size() - 1; i++) {
        if (V[i] == x) swap(V[i], V[i + 1]); 
    }
    assert(V.back() == x);
    return V;
}

vector<int> beg(vector<int> V, int x) {
    for (int i = (int)V.size() - 1; i > 0; i--) {
        if (V[i] == x) swap(V[i], V[i - 1]); 
    }
    assert(V[0] == x);
    return V;
}

vector<int> connect(vector<int> A, vector<int> B) {
    for (int i = 0; i < (int)B.size() - 1; i++) {
        if (are_con({A.back()}, {B[i]})) {
            return A + beg(B, B[i]);
        }
    }
    return A + beg(B, B.back());
};

info recursion(vector<int> V) {
    if ((int)V.size() == 1) 
        return {V, {}, V};
    vector<int> A, B;
    vector<bool> us(N);
    int p = V[rnd() % (int)V.size()];
    cerr << "chosen vertex: " << p << '\n';
    for (int c : V) if (p != c) {
        if (!are_con({p}, {c})) {
            B.push_back(c);
            us[c] = true;
        }
    }
    if (B.empty()) {
        info res;
        cerr << p << " is a star\n";
        V.erase(find(V.begin(), V.end(), p));
        info m = recursion(V);
        if (m.ord.empty()) {
            res.ord = m.A + vector<int>{p} + m.B;
        } else {
            res.ord = m.ord;
            res.ord.push_back(p);
        }
        return res;
    }
    for (int c : V) {
        if (us[c]) continue;
        if (!are_con({c}, B)) {
            A.push_back(c);
            us[c] = true;
        }
    }
    cerr << "Division: \n";
    print(A);
    print(B);
    cerr << '\n';

    vector<int> v1;
    for (int c : V) 
        if (!us[c]) 
            v1.push_back(c);
    if (v1.empty()) 
        return {A, B, {}};

    info M = recursion(v1);
    info res;
    
    if (!M.ord.empty()) {
        res.ord = fin(A, p) + connect(M.ord, B);
        return res;
    }
    for (int it = 0; it < 2; it++) {
        if ((int)A.size() == 1) {
            res.ord = M.A + A + connect(M.B, B);
            return res;       
        }
        swap(A, B);
    }
    int c = A[(A[0] == p)], t = M.A[0];
    if (are_con({c}, {t})) {
        res.ord = fin(M.A, t) + beg(fin(A, p), c) + connect(M.B, B);
    } else {
        res.ord = fin(A, p) + connect(M.B, B) + beg(M.A, t);  
    }
    return res;
}


vector<int> longest_trip(int N_ins, int D) {
    N = N_ins;
    // for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
    //     g[i][j] = 0;
    // for (int i = 0; i < N; i++)
    //     for (int j = i + 1; j < N; j++) {
    //         g[i][j] = g[j][i] = are_connected({i}, {j});
    //     }
    
    vector<int> v(N);
    for (int i = 0; i < N; i++) v[i] = i;
    info res = recursion(v);
    if (res.ord.empty()) {
        if ((int)res.A.size() < (int)res.B.size())
            swap(res.A, res.B);
        return res.A;
    }
    return res.ord;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 113 ms 344 KB Output is correct
4 Correct 339 ms 676 KB Output is correct
5 Correct 691 ms 1244 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 118 ms 344 KB Output is correct
4 Correct 340 ms 1108 KB Output is correct
5 Correct 676 ms 1192 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 27 ms 340 KB Output is correct
8 Correct 129 ms 344 KB Output is correct
9 Correct 279 ms 600 KB Output is correct
10 Incorrect 138 ms 908 KB too many calls
11 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 22 ms 344 KB Output is correct
3 Correct 128 ms 600 KB Output is correct
4 Correct 343 ms 600 KB Output is correct
5 Correct 650 ms 1224 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 115 ms 600 KB Output is correct
9 Correct 279 ms 600 KB Output is correct
10 Incorrect 178 ms 980 KB too many calls
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Partially correct 127 ms 344 KB Output is partially correct
4 Partially correct 325 ms 720 KB Output is partially correct
5 Partially correct 673 ms 828 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Partially correct 126 ms 344 KB Output is partially correct
9 Partially correct 284 ms 592 KB Output is partially correct
10 Incorrect 166 ms 1248 KB too many calls
11 Halted 0 ms 0 KB -