Submission #1060020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060020		epicci23	Longest Trip (IOI23_longesttrip)	C++17	30 / 100	874 ms	1520 KiB

longesttrip

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
#include "longesttrip.h"

vector<int> v[260];
vector<int> vis(260,0),vis2(260,0),depth(260,-1),topo;
int ord[260],max_c,max_ans,max_a,max_b;
vector<int> aa,bb;

void topo_sort(int c){
  if(vis[c]) return;
  vis[c]=1;
  for(int x:v[c]) topo_sort(x);
  topo.push_back(c);
}

void dfs(int c,int p){
  if(vis[c]) return;
  vis[c]=1;
  sort(all(v[c]),[&](int a,int b){
    return ord[a]<ord[b];
  });
  vector<array<int,2>> takla;
  for(int x:v[c]){
  	 if(x==p) continue;
  	 if(!vis[x]){
  	 	dfs(x,c);
  	 	depth[c]=max(depth[c],depth[x]);
  	 	takla.push_back({depth[x],x});
  	 }
  }
  depth[c]++;
  sort(all(takla));
  reverse(all(takla));
  if(sz(takla)<=1) return;
  if(takla[0][0]+takla[1][0]+1>max_ans){
  	max_ans=takla[0][0]+takla[1][0]+1;
  	max_c=c;
  	max_a=takla[0][1];
  	max_b=takla[1][1];
  }
}

void go_leaf(int c,int t){
  if(vis[c]) return;
  vis[c]=1;
  int kid=-1,maxi=-1;
  for(int x:v[c]){
  	if(depth[x]>=depth[c]) continue;
  	if(depth[x]>maxi){
      maxi=depth[x];
      kid=x;
  	}
  }
  if(kid!=-1) go_leaf(kid,t);
  if(t) aa.push_back(c);
  else bb.push_back(c);
}

void mark(int c){
  if(vis2[c]) return;
  vis2[c]=1;
  for(int x:v[c]) mark(x);
}
 
vector<int> construct(int c){
  vector<int> res;
  topo.clear();aa.clear();bb.clear();
  vis.assign(260,0);
  depth.assign(260,-1);
  topo_sort(c);
  reverse(all(topo));
  for(int i=0;i<sz(topo);i++) ord[topo[i]]=i;
  vis.assign(260,0);
  max_a=max_b=max_ans=max_c=-1;
  dfs(c,-1);
  vis.assign(260,0);
  if(max_a!=-1) go_leaf(max_a,1);
  vis.assign(260,0);
  if(max_b!=-1) go_leaf(max_b,0);
  if(max_a!=-1){
    aa.push_back(max_c);
    reverse(all(bb));
    for(int uu:bb) aa.push_back(uu);
    if(sz(aa)>sz(res)) res=aa;
  }
  aa.clear();
  go_leaf(c,1);
  if(sz(aa)>sz(res)) res=aa;
  return res;
}


vector<int> longest_trip(int n, int d){
  if(d==3){
  	vector<int> res(n,0);
  	iota(all(res),0);
  	return res;
  }
  for(int i=0;i<n;i++) v[i].clear();
  for(int i=0;i<n;i++){
  	for(int j=i+1;j<n;j++){
  	  if(are_connected({i},{j})){
  	  	v[i].push_back(j);
  	  	v[j].push_back(i);
  	  }	
  	}
  }
  vector<int> ans;
  vis2.assign(260,0);
  for(int i=0;i<n;i++){
  	if(vis2[i]) continue;
    vector<int> x=construct(i);
    if(sz(x)>sz(ans)) ans=x;
    mark(i);
  }
  return ans;
}

/*void _(){
  int n,m;
  cin >> n >> m;
  for(int i=0;i<n;i++) v[i].clear();
  for(int i=0;i<m;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }
  vector<int> ans;
  for(int i=0;i<n;i++){
  	vector<int> x=construct(i);
  	if(sz(x)>sz(ans)) ans=x;
  }
  for(int x:ans) cout << x << ' ';
  cout << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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