Submission #1038246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038246		aymanrs	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	51 ms	860 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int g[257][257] = {{0}};
bool isg(int a, int b){
    if(g[a][b]) {
        return g[a][b] == 1;
    }
    if(are_connected({a},{b})){
        g[a][b]=g[b][a]=1;
        return true;
    }
    g[a][b]=g[b][a]=-1;
    return false;
}
bool arc(const vector<int>& a, const vector<int>& b){
    if(a.empty()||b.empty()) return false;
    bool at0=false;
    for(int i : a) for(int j : b) {
        if(g[i][j]==1) return true;
        else if(!g[i][j]) at0=true;
    }
    if(!at0) return false;
    return are_connected(a, b);
}
pair<vector<int>,vector<int>> fl(const vector<int>& V){
    if(V.size()<=1) return {V, {}};
    int i, j;
    vector<int> a;a.push_back(V[0]);
    for(i = 1;i < V.size();i++){
        if(isg(a.back(), V[i])){
            a.push_back(V[i]);
        } else {
            i = V[i];
            j = a.back();
            break;
        }
    }
    if(a.size() == V.size()) return {a, {}};
    vector<int> b, c;
    a.clear();
    for(int k : V){
        if(k==i||k==j) continue;
        if(!isg(k,j)) a.push_back(k);
        else if(!isg(k,i)) c.push_back(k);
        else {
            b.push_back(k);
        }
    }
    if(b.empty()){
        if(!arc(a,c)) {
            a.push_back(i);
            c.push_back(j);
            return {a,c};
        }
        int l=0,r=c.size()-1, ll=0,rr=a.size()-1;
        while(l<r||ll<rr){
            if(r-l > rr-ll){
                int m = r+l>>1;
                if(arc(vector<int>{c.begin()+l,c.begin()+m+1}, vector<int>{a.begin()+ll,a.begin()+rr+1})){
                    r=m;
                } else l = m+1;
            } else {
                int m = ll+rr>>1;
                if(arc(vector<int>{c.begin()+l,c.begin()+r+1}, vector<int>{a.begin()+ll,a.begin()+m+1})){
                    rr=m;
                } else ll = m+1;
            }
        }
        a.push_back(i);swap(a[ll], a.back());
        c.push_back(j);swap(c[l], c[0]);
        for(int k : c) a.push_back(k);
        return {a, {}};
    }
    auto L = fl(b);
    if(L.second.empty()){
        a.push_back(i);
        for(int k : L.first) a.push_back(k);
        a.push_back(j);
        for(int k : c) a.push_back(k);
        return {a, {}};
    } else {
        if(a.empty()){
            L.first.push_back(i);
            for(int k : L.second) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
        if(isg(a[0], L.first[0])){
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.first) a.push_back(k);
            for(int k : a) L.second.push_back(k);
            L.second.push_back(j);
            for(int k : c) L.second.push_back(k);
            return {L.second, {}};
        } else {
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.second) a.push_back(k);
            for(int k : a) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
    }

}
std::vector<int> longest_trip(int N, int D)
{
    vector<int> V;
    for(int i = 0;i < N;i++) {
        V.push_back(i);
        for(int j = 0;j < N;j++) g[i][j] = 0;
    }
    auto L = fl(V);
    if(L.first.size()>=L.second.size()) return L.first;
    return L.second;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > fl(const std::vector<int>&)':
longesttrip.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(i = 1;i < V.size();i++){
      |               ~~^~~~~~~~~~
longesttrip.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |                 int m = r+l>>1;
      |                         ~^~
longesttrip.cpp:66:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |                 int m = ll+rr>>1;
      |                         ~~^~~

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