Submission #840068

#	Time	Username	Problem	Language	Result	Execution time	Memory
840068		Fysty	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	1035 ms	1004 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"

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

void dfs(int u)
{
    vis[u]=1;
    for(int v:ed[u]) if(!vis[v])
    {
        par[v]=u;
        cnt[u]++;
        dfs(v);
    }
}

void dfs2(int u,vector<int> &ret)
{
    vis[u]=1;
    ret.pb(u);
    for(int v:ed[u]) if(!vis[v]) dfs2(v,ret);
}



/*bool db[300][300];

bool are_connected(vector<int> a,vector<int> b)
{
    bool ret=0;
    for(int x:a) for(int y:b)
    {
        ret|=db[x][y];
    }
    return ret;
}*/

vector<int> longest_trip(int N,int D)
{
    n=N;
    rep(i,n)
    {
        rep(j,n)
        {
            has[i][j]=0;
        }
        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;
    }
    rep(i,n) rep(j,i)
    {
        bool res=are_connected({i},{j});
        if(res)
        {
            ed[i].pb(j);
            ed[j].pb(i);
            has[i][j]=has[j][i]=1;
            deg[i]++,deg[j]++;
        }
    }
    par[0]=-1;
    dfs(0);
    vector<int> a,b;
    rep(i,n)
    {
        if(vis[i]) a.pb(i);
        else b.pb(i);
    }
    if(!b.empty())
    {
        if(a.size()>b.size()) return a;
        else return b;
    }
    /*int r=-1;
    rep(i,n)
    {
        vis[i]=0;
        if(deg[i]==1) r=i;
    }
    if(r!=-1)
    {
        dfs2(r,ret);
        return ret;
    }*/
    rep(i,n) vis[i]=0;
    vector<int> tmp;
    int x;
    rep(i,n)
    {
        if(cnt[i]==0) tmp.pb(i);
        if(cnt[i]==2) x=i;
    }
    if(tmp.size()==1)
    {
        int cur=tmp[0];
        while(cur!=-1)
        {
            ret.pb(cur);
            cur=par[cur];
        }
        return ret;
    }
    vector<int> ret2;
    int cur=tmp[0];
    while(cur!=par[x])
    {
        ret.pb(cur);
        cur=par[cur];
    }
    cur=tmp[1];
    while(cur!=x)
    {
        ret2.pb(cur);
        cur=par[cur];
    }
    reverse(ret2.begin(),ret2.end());
    for(int v:ret2) ret.pb(v);
    if(x==0) return ret;

    vector<int> ret3;
    cur=par[x];
    while(cur!=-1)
    {
        ret3.pb(cur);
        cur=par[cur];
    }
    if(has[par[x]][tmp[0]])
    {
        reverse(ret.begin(),ret.end());
    }
    for(int v:ret3) ret.pb(v);
    return ret;
}

/*
void solve()
{
    int N,D;
    cin>>N>>D;
    rep(i,N)
    {
        rep(j,N) cin>>db[i][j];
    }
    auto ans=longest_trip(N,D);
    for(int x:ans) cout<<x<<" ";
}

signed main()
{
    MottoHayaku

    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}*/

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:173:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  173 |     cur=par[x];
      |         ~~~~~^

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