Submission #1020194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020194		bobbilyking	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	1 ms	600 KiB

longesttrip

#include "longesttrip.h"
using namespace std;
#include <bits/stdc++.h>
 
#define F(i, l, r) for (int i = (l); i < (r); ++i)
#define A(a) (a).begin(), (a).end()
 
int edge[300][300];
int parent[300];
int find(int i) {
    return i == parent[i] ? i : parent[i] = find(parent[i]);
}

void add_edge(int A, int B) {
    edge[A][B] = edge[B][A] = 1;
    parent[find(A)] = find(B);
}
 
bool query(vector<int> A, vector<int> B) {
    // for (auto x: A ) cout << x << " "; cout << endl;
    // for (auto x: B ) cout << x << " "; cout << endl;
    

    if (A.size() == 1 and B.size() == 1) {
        if (edge[A[0]][B[0]]) return 1;
    }
 
    bool res = are_connected(A, B);
 
    if (res) {
        if (A.size() == 1 and B.size() == 1) {
            add_edge(A[0], B[0]);
        }
    }
 
    return res; 
}
 
vector<int> longest_trip(int N, int D)
{
    iota(parent, parent + N, 0ll);
    memset(edge, 0, sizeof edge);
 
    deque<int> hamil;
 
    auto gen = [&]() {
        set<int> v;
        vector<bool> seen(N+1);
        for (auto x: hamil) seen[x] = 1;
        F(i, 0, N) if (!seen[i]) v.insert(i);
        return v;
    };
 
    if (query({0}, {1})) {
        hamil = {0, 1};
    } else if (query({1}, {2})) {
        hamil = {1, 2};
    } else {
        add_edge(0, 2);
        hamil = {0, 2};
    }
 
    while (hamil.size() != N) { // this will reach N, with the exception of one case 
        for (auto x: hamil) cout << x << " "; cout << endl;;

        // Mandatory 1 query here.
        // If we go into other branch, good, we only need 2 queries at most.  

        if (query({hamil[0]}, {hamil.back()})) {
            // behaves as hamil cycle 
        } else {
            // Pick any node not in hamil, this must be connected to either the front or the back.
            auto i = *gen().begin();
 
            // cout << "HAHA " << endl;
            if (query({hamil[0]}, {i})) hamil.push_front(i);
            else {
                add_edge(hamil.back(), i);
                hamil.push_back(i);
            }
            continue;
        }
        
 
        // Okay, we want to find *any* connection between hamil and others, if exists already. 
        auto bad = gen();
 
        bool seen_edge = false;

        auto prev = hamil;
        F(i, 0, hamil.size()) {
            auto v = hamil.back(); hamil.pop_back(); hamil.push_front(v); 
            for (auto y: bad) if (edge[v][y]) {
                hamil.push_front(y);
                seen_edge = 1;
                goto end;
            }
        }
        end: if (seen_edge) continue;

        assert(prev == hamil);

        // cout << " ivaldf " << endl;
 
        // Okay, now we want to do the "pick one from end, and two disjoint components" strategy.
        while (true) {
            int state = 0;
            // Amortized shit; 
            // OOOH. But here it *can* overlap, we pay 1 mandatory per thing and 2 mandatory per amortized, so in total
            // 3N queries worst case... hmm...

            for (auto x: bad) for (auto y: bad) if (find(x) != find(y)) {
                // cout << "YA " << x << " " << y << endl;
                if (query({x}, {y})) {
                    // cout << "Shitty " << endl;
                    state = 1; goto end2; // incr spanning tree, okay.
 
                } else { // actually no edge between these, therefore one end MUST connect to hamil[0].
                    state = 2; 
                    // cout << " HOW THO " << x << " " << y << " " << hamil[0] << endl;
                    if (query({x}, {hamil[0]})) {
                        hamil.push_front(x);
                    } else {
                        add_edge(hamil[0], y);
                        hamil.push_front(y);
                    }
                    goto end2;
                }
            }
            end2:
            if (state == 1) continue;
            if (state == 2) break; 
 
            // Mandatory pay once, 2 * log(n) queries 

            // OTHERWISE, RARE ONCE IN AN ITERATION CASE: WE ASK IF THERE'S ANY CONNECTION ACROSS BOTH COMPS.
 
            // IF NOT, THEN INSTANTLY KNOW TWO K_N COMPS.

            // cout << "CHECKING KN " << endl;
 
            if (!query(vector<int>(A(hamil)), vector<int>(A(bad)))) {
                if (hamil.size() < bad.size()) {
                    return vector<int>(A(bad));
                }
                return vector<int>(A(hamil));
            }
            
            // ELSE, FIND ANY SPANNING EDGE WITH BSEARCH, TAKE IT. BREAK, WE WILL FIND THE SPANNING EDGE AGAIN NEXT LOOP. 
 
            vector<int> cur(A(bad));
            while (cur.size() > 1) {
                vector<int> shit(cur.begin(), cur.begin() + cur.size()/2);
                if (query(vector<int>(A(hamil)), shit)) cur = shit;
                else cur = vector<int>(cur.begin() + cur.size() / 2, cur.end());
            }
 
            int x = cur[0];
 
            cur = vector<int>(A(hamil));
            while (cur.size() > 1) {
                vector<int> shit(cur.begin(), cur.begin() + cur.size()/2);
                if (query({x}, shit)) cur = shit;
                else cur = vector<int>(cur.begin() + cur.size() / 2, cur.end());
            }
 
            int y = cur[0];

            add_edge(x, y);
            break;
        }
 
        // cout << "WHILE TRUING " << endl;
    }
 
 
    return vector<int>(A(hamil));
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:63:25: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     while (hamil.size() != N) { // this will reach N, with the exception of one case
      |            ~~~~~~~~~~~~~^~~~
longesttrip.cpp:64:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |         for (auto x: hamil) cout << x << " "; cout << endl;;
      |         ^~~
longesttrip.cpp:64:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |         for (auto x: hamil) cout << x << " "; cout << endl;;
      |                                               ^~~~
longesttrip.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define F(i, l, r) for (int i = (l); i < (r); ++i)
      |                                        ^
longesttrip.cpp:91:9: note: in expansion of macro 'F'
   91 |         F(i, 0, hamil.size()) {
      |         ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60