Submission #1240577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240577		dosts	Longest Trip (IOI23_longesttrip)	C++20	30 / 100	5 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

std::vector<int> longest_trip(int N, int D)
{   
    vi trip1,trip2;
    trip1.push_back(0);
    vi uc;
    uc.push_back(0);
    for (int i=1;i<N;i++) {
        if (uc.size() == 1) {
            if (are_connected({trip1.back()},{i})) trip1.push_back(i);
            else {
                uc.push_back(i);
                trip2.push_back(i);
                continue;
            }
        }
        else {
            int f1 = are_connected({trip1.back()},{i});
            int f2 = are_connected({trip2.back()},{i});
            if (!f1 && !f2) assert(0);
            if (f1  && f2) {
                reverse(all(trip2));
                trip1.push_back(i);
                for (auto it : trip2) trip1.push_back(it);
                trip2.clear();
                uc.pop_back();
                continue;
            }
            if (f1) {
                trip1.push_back(i);
            } else trip2.push_back(i);
        }
    }
    if (trip1.size() > trip2.size()) return trip1;
    return trip2;
}

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