Submission #1228711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228711		virgoliny	Longest Trip (IOI23_longesttrip)	C++20	40 / 100	469 ms	1584 KiB

longesttrip

#include "longesttrip.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> adj, dist;
vector<bool> vis;
inline void dfs(ll n, ll p){
vis[n]=1;
for(auto y: adj[n]){
if(vis[y] || dist[p][n]+1<dist[p][y])continue;
dist[p][y]=dist[p][n]+1;
dfs(y, p);
}
vis[n]=0;
}
std::vector<int> longest_trip(int N, int D){
    vector<int> v;
    vector<vector<ll>>().swap(adj);
    vector<vector<ll>>().swap(dist);
    vector<bool>().swap(vis);
    vis.assign(N+1, 0);
    adj.resize(N+1);
    dist.assign(N+1, vector<ll>(N+1, LLONG_MIN));
    for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
    if(are_connected({i}, {j})){
    adj[i].push_back(j);
    adj[j].push_back(i);
    //cout<<i<<" "<<j<<endl;
    }
    }
    }
    for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
    vis[j]=0;
    }
    dist[i][i]=0;
    dfs(i, i);
    }
    ll o=-1, o1, o2;
    for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
    if(dist[i][j]>o && dist[i][j]!=LLONG_MAX){o=dist[i][j];o1=i;o2=j;}
    //cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
    }
    }
    //cout<<1<<" "<<o1<<" "<<o2<<endl;
    v.push_back(o2);
    while(o2!=o1){
    for(auto y: adj[o2]){
    if(dist[o1][y]+1==dist[o1][o2]){
    v.push_back(y);
    o2=y;
    continue;
    }
    }
    }
    return v;
}

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