oj.uz

Submission #1059997

# Submission time Handle Problem Language Result Execution time Memory
1059997 2024-08-15T09:57:24 Z epicci23 Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 1052 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];
  });
  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){
  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 _(){
  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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 362 ms 736 KB Output is correct

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 167 ms 600 KB Output is correct
4 Correct 570 ms 492 KB Output is correct
5 Execution timed out 1490 ms 960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 172 ms 344 KB Output is correct
4 Correct 569 ms 596 KB Output is correct
5 Execution timed out 1487 ms 936 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Partially correct 145 ms 340 KB Output is partially correct
4 Partially correct 572 ms 704 KB Output is partially correct
5 Execution timed out 1490 ms 1052 KB Time limit exceeded
6 Halted 0 ms 0 KB -