oj.uz

Submission #1059973

# Submission time Handle Problem Language Result Execution time Memory
1059973 2024-08-15T09:46:02 Z epicci23 Longest Trip (IOI23_longesttrip) C++17
5 / 100
 4 ms 596 KB 
#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[300];
vector<int> vis(300,0),depth(300,-1),topo;
int ord[300],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];
  });
  for(int x:v[c]){
  	 if(x==p) continue;
  	 dfs(x,c);
     depth[c]=max(depth[c],depth[x]);
  }
  depth[c]++;
  vector<array<int,2>> takla;
  for(int x:v[c]){
    if(x==p) continue;
    takla.push_back({depth[x],x});
  }
  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){
  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);
}
 
vector<int> construct(int c){
  vector<int> res;
  topo.clear();aa.clear();bb.clear();
  vis.assign(300,0);
  depth.assign(300,-1);
  topo_sort(c);
  reverse(all(topo));
  for(int i=0;i<sz(topo);i++) ord[topo[i]]=i;
  vis.assign(300,0);
  max_a=max_b=max_ans=max_c=-1;
  dfs(c,-1);
  vis.assign(300,0);
  if(max_a!=-1) go_leaf(max_a,1);
  vis.assign(300,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;
  for(int i=0;i<n;i++){
  	vector<int> x=construct(i);
  	if(sz(x)>sz(ans)) ans=x;
  }
  return ans;
}

/*void _(){
	
}

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -