oj.uz

Submission #980026

# Submission time Handle Problem Language Result Execution time Memory
980026 2024-05-11T19:27:10 Z logangd Longest Trip (IOI23_longesttrip) C++17
5 / 100
 7 ms 600 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N, int D){
	vector<int> r1,r2,R;
	r1.push_back(0);
	for(int i=1;i<N;i++){
		vector<int>e1,e2,e3,e4;
		if(!r2.empty()){
			e1.push_back(r1.back());
			e2.push_back(r2.back());
			if(are_connected(e1,e2)){
				while(!r2.empty()){
					r1.push_back(r2.back());
					r2.pop_back();
				}
			}
		}
		e3.push_back(r1.back());
		e4.push_back(i);
		if(are_connected(e3,e4))r1.push_back(i);
		else r2.push_back(i);		
	}
	if(r2.empty())return r1;
	vector<int>e1,e2,e3,e4;
	e1.push_back(r1[0]);
	e2.push_back(r1.back());
	e3.push_back(r2[0]);
	e4.push_back(r2.back());
	if(!are_connected(e1,e2)){
		if(are_connected(e1,e3))reverse(r1.begin(),r1.end());
		reverse(r2.begin(),r2.end());
		while(!r2.empty()){
			r1.push_back(r2.back());
			r2.pop_back();
		}
		return r1;
	}
	if(!are_connected(e3,e4)){
		if(are_connected(e1,e3))reverse(r2.begin(),r2.end());
		reverse(r1.begin(),r1.end());
		while(!r1.empty()){
			r2.push_back(r1.back());
			r1.pop_back();
		}
		return r2;
	}
	else if(are_connected(r1,r2)){
		vector<int>t_1,t_2;
		for(auto i:r1)t_1.push_back(i);
		while(1<t_1.size()){
			vector<int>t1,t2;
			int p=0;
			for(auto i:t_1){
				if(p&1)t1.push_back(i);
				else t2.push_back(i);
				p++;
			}
			if(are_connected(t1,r2))swap(t_1,t1);
			else swap(t_1,t2);
		}
		for(auto i:r2)t_2.push_back(i);
		while(1<t_2.size()){
			vector<int>t1,t2;
			int p=0;
			for(auto i:t_2){
				if(p&1)t1.push_back(i);
				else t2.push_back(i);
				p++;
			}
			if(are_connected(t_1,t1))swap(t_2,t1);
			else swap(t_2,t2);
		}
		bool b=0;
		for(auto i:r1){
			if(b)R.push_back(i);
			if(i==t_1[0])b=1;
		}
		for(auto i:r1){
			R.push_back(i);
			if(i==t_1[0])break;
		}
		b=0;
		for(auto i:r2){
			if(i==t_2[0])b=1;
			if(b)R.push_back(i);
		}
		for(auto i:r2){
			if(i==t_2[0])break;
			R.push_back(i);
		}
		return R;
	}else if(r1.size()>r2.size())return r1;
	else return r2;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB non-disjoint arrays
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB non-disjoint arrays
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB non-disjoint arrays
7 Halted 0 ms 0 KB -