Submission #1202710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202710		PagodePaiva	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	6 ms	436 KiB

longesttrip

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

using namespace std;

const int N = 260;

bool query(vector <int> a, vector <int> b){
    /*for(auto x : a)
        cout << x << ' ';
    cout << '\n';
    for(auto x : b)
        cout << x << ' ';
    cout << '\n';
    cout << '\n';*/
    if(a == b)
        return false;
    return are_connected(a, b);
}

vector<int> longest_trip(int n, int D){
    queue <vector <int>> pq;
    for(int i = 0;i < n;i++){
        pq.push({i});
    }
    while(pq.size() > 2){
        vector <int> a = pq.front();
        pq.pop();
        vector <int> b = pq.front();
        pq.pop();
        vector <int> c = pq.front();
        pq.pop();
        if(query({a.back()}, {b.back(), c.back()})){
            if(!query({a.back()}, {b.back()})){
                swap(b, c);
            }
            reverse(b.begin(), b.end());
            for(auto x : b)
                a.push_back(x);
            pq.push(a);
            pq.push(c);
        }
        else{
            reverse(b.begin(), b.end());
            for(auto x : b)
                c.push_back(x);
            pq.push(a);
            pq.push(c);            
        }
    }
    vector <int> a = pq.front();
    pq.pop();
    vector <int> c = pq.front();
    pq.pop();
    if(!query(a, c)){
        if(a.size() < c.size())
            swap(a, c);
        return a;
    }
    if(!query({c[0]}, {c.back()}))
        swap(a, c);
    if(!query({a[0]}, {a.back()})){
        if(query({a[0]}, {c[0]})){
            reverse(a.begin(), a.end());
            for(auto x : c)
                a.push_back(x);
            return a;
        }
        else{
            reverse(c.begin(), c.end());
            for(auto x : c)
                a.push_back(x);
            return a;
        }
    }
    for(auto x : a){
        if(are_connected({x}, c)){
            for(auto y : c){
                if(are_connected({x}, {y})){
                    while(a.back() != x){
                        int t = a[0];
                        reverse(a.begin(), a.end());
                        a.pop_back();
                        reverse(a.begin(), a.end());
                        a.push_back(t);
                    }
                    while(c.back() != y){
                        int t = c[0];
                        reverse(c.begin(), c.end());
                        c.pop_back();
                        reverse(c.begin(), c.end());
                        c.push_back(t);
                    }
                    reverse(c.begin(), c.end());
                    for(auto x : c)
                        a.push_back(x);
                    return a;
                }
            }
        }
    }
    return a;
}

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