Submission #1228710

#TimeUsernameProblemLanguageResultExecution timeMemory
1228710virgolinyLongest Trip (IOI23_longesttrip)C++20
0 / 100
4 ms408 KiB
#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; inline void bfs(ll n){ queue<pair<ll, ll>> q; dist[n][n]=0; q.push({0, n}); while(!q.empty()){ ll o, o1; tie(o, o1)=q.front(); q.pop(); for(auto y: adj[o1]){ if(dist[n][y]>o+1){ dist[n][y]=o+1; q.push({o+1, y}); } } } } std::vector<int> longest_trip(int N, int D){ vector<int> v; //cerr<<1<<endl; vector<vector<ll>>().swap(adj); vector<vector<ll>>().swap(dist); adj.resize(N+1); dist.assign(N+1, vector<ll>(N+1, LLONG_MAX)); 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++)bfs(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; break; } } } return v; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...