Submission #1233274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233274		Sir_Ahmed_Imran	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	5 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int n;

vector<int> solve3(){
    vector<int> v;
    for(int i = 0; i < n; i++)
        v.append(i);
    return v;
}

vector<int> solve2(){
    deque<int> Q;
    Q.append(0);
    if(are_connected({0}, {1})){
        Q.append(1);
        if(are_connected({1}, {2}))
            Q.append(2);
        else Q.push_front(2);
    }
    else
        Q.append(2), Q.append(1);
    for(int i = 3; i < n; i++){
        if(are_connected({Q.back()}, {i}))
            Q.append(i);
        else Q.push_front(i);
    }
    vector<int> ans;
    while(!Q.empty()){
        ans.append(Q.front());
        Q.pop_front();
    }
    return ans;
}

vector<int> solve1(){
    deque<int> d, q;
    d.append(0);
    vector<int> ans;
    for(int i = 1; i < n; i++){
        if(are_connected({d.back()}, {i})){
            d.append(i);
            if(!q.empty() && are_connected({i}, {q.back()})){
                while(!q.empty()){
                    d.append(q.back());
                    q.pop_back();
                }
            }
        }
        else q.append(i);
    }
    if(d.size() < q.size()) swap(d, q);
    while(!d.empty()){
        ans.append(d.front());
        d.pop_front();
    }
    return ans;
}

vector<int> longest_trip(int N, int D){
    n = N;
    if(D == 3)
        return solve3();
    if(D == 2)
        return solve2();
    return solve1();
}

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