Submission #840262

#	Time	Username	Problem	Language	Result	Execution time	Memory
840262		Fysty	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	14 ms	704 KiB

longesttrip

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

#include "longesttrip.h"

int has[300][300];
vector<int> ed[300];
bool vis[300];
int par[300];
int deg[300],cnt[300];
int n;


vector<int> longest_trip(int N,int D)
{
    n=N;
    rep(i,n)
    {
        rep(j,n)
        {
            has[i][j]=-1;
        }
        ed[i].clear();
        vis[i]=0;
        par[i]=-1;
        deg[i]=cnt[i]=0;
    }
    vector<int> ret;
    if(D==3)
    {
        rep(i,n) ret.pb(i);
        return ret;
    }
    vector<int> v1={0},v2;
    bool has=1;
    rep1(i,n-1)
    {
        if(are_connected({v1.back()},{i}))
        {
            v1.pb(i);
            has=1;
        }
        else if(has==0)
        {
            v2.pb(i);
        }
        else
        {
            if(v2.empty()||are_connected({v2.back()},{i}))
            {
                v2.pb(i);
                has=0;
            }
            else
            {
                reverse(v2.begin(),v2.end());
                for(int x:v2) v1.pb(x);
                v2={i};
                has=1;
            }
        }
    }
    if(v1.size()<v2.size()) swap(v1,v2);
    if(v2.empty()) return v1;
    if(!are_connected(v1,v2)) return v1;
    if(are_connected({v1[0]},{v2[0]}))
    {
        reverse(v2.begin(),v2.end());
        for(int x:v1) v2.pb(x);
        return v2;
    }
    if(are_connected({v1.back()},{v2[0]}))
    {
        for(int x:v2) v1.pb(x);
        return v1;
    }
    int l=0,r=(int)v1.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        vector<int> tmp;
        rep(i,mid+1) tmp.pb(v1[i]);
        if(are_connected(tmp,{v2[0]})) r=mid;
        else l=mid+1;
    }
    reverse(v2.begin(),v2.end());
    for(int i=l;i<v1.size();i++) v2.pb(v1[i]);
    rep(i,l) v2.pb(v1[i]);
    return v2;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:117:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |         int mid=l+r>>1;
      |                 ~^~
longesttrip.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i=l;i<v1.size();i++) v2.pb(v1[i]);
      |                 ~^~~~~~~~~~

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