oj.uz

Submission #1067335

# Submission time Handle Problem Language Result Execution time Memory
1067335 2024-08-20T15:10:17 Z pcc Longest Trip (IOI23_longesttrip) C++17
100 / 100
 15 ms 856 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>

const int mxn = 300;

int N;
int dp[mxn][mxn];

int ask(vi a,vi b){
	return are_connected(a,b);
}
int ask(int a,int b){
	if(a == b)return 1;
	if(dp[a][b] != -1)return dp[a][b];
	return dp[a][b] = dp[b][a] = ask(vi({a}),vi({b}));
}

vi to_vec(deque<int> a){
	vi re;
	for(auto &i:a)re.push_back(i);
	return re;
}
int ask(deque<int> a,deque<int> b){
	return ask(to_vec(a),to_vec(b));
}

std::vector<int> longest_trip(int NN, int D){
	memset(dp,-1,sizeof(dp));
	deque<int> dq[2];
	N = NN;
	set<int> st;
	for(int i =0;i<N;i++)st.insert(i);
	if(ask(0,1))dq[0] = {0,1};
	else if(ask(0,2))dq[0] = {0,2};
	else dq[0] = {1,2};
	for(auto &i:dq[0])st.erase(i);
	while(st.size()){
		if(dq[1].empty()){
			dq[1].push_back(*st.begin());
			st.erase(*st.begin());
			continue;
		}
		vector<int> now;
		for(int i = 0;i<2&&!st.empty();i++){
			now.push_back(*st.begin());
			st.erase(*st.begin());
		}
		if(now.size() == 1){
			int tmp = now[0];
			if(ask(dq[0].back(),tmp))dq[0].push_back(tmp);
			else if(ask(dq[1].back(),tmp))dq[1].push_back(tmp);
			else{
				while(!dq[1].empty()){
					dq[0].push_back(dq[1].back());
					dq[1].pop_back();
				}
				dq[1] = {tmp};
			}
		}
		else{
			int a = now[0],b = now[1];
			if(ask(a,b)){
				if(ask(dq[0].back(),a)){
					dq[0].push_back(a);
					dq[0].push_back(b);
				}
				else if(ask(dq[1].back(),a)){
					dq[1].push_back(a);
					dq[1].push_back(b);
				}
				else{
					while(!dq[1].empty()){
						dq[0].push_back(dq[1].back());
						dq[1].pop_back();
					}
					dq[1] = {a,b};
				}
			}
			else{
				if(ask(dq[0].back(),a)){
					dq[0].push_back(a);
				}
				else{
					swap(a,b);
					dq[0].push_back(a);
				}
				if(ask(dq[1].back(),b)){
					dq[1].push_back(b);
				}
				else{
					//assert(ask(dq[1].back(),dq[0].back()));
					while(!dq[1].empty()){
						dq[0].push_back(dq[1].back());
						dq[1].pop_back();
					}
					dq[1] = {b};
				}
			}
			if(dq[0].size()<dq[1].size())dq[0].swap(dq[1]);
		}
	}

	/*
	cerr<<"PHASE 1 done!"<<endl;
	cerr<<"DQ[0]: "<<endl;for(auto &i:dq[0])cerr<<i<<',';cerr<<endl;
	cerr<<"DQ[1]: "<<endl;for(auto &i:dq[1])cerr<<i<<',';cerr<<endl;cerr<<"--------------------------------"<<endl;
	for(int i = 1;i<dq[0].size();i++)assert(ask(dq[0][i-1],dq[0][i]));
	for(int i = 1;i<dq[1].size();i++)assert(ask(dq[1][i-1],dq[1][i]));
	*/
	assert(dq[0].size()>=dq[1].size());
	if(dq[1].empty()||!ask(dq[0],dq[1])){
		return to_vec(dq[0]);
	}
	//cerr<<"CHECK CHAIN DONE!"<<endl;
	if(ask(dq[0][0],dq[1][0])){
		while(!dq[1].empty()){
			dq[0].push_front(dq[1][0]);
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0][0],dq[1].back())){
		while(!dq[1].empty()){
			dq[0].push_front(dq[1].back());
			dq[1].pop_back();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0].back(),dq[1][0])){
		while(!dq[1].empty()){
			dq[0].push_back(dq[1].front());
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0].back(),dq[1].back())){
		while(!dq[1].empty()){
			dq[0].push_back(dq[1].back());
			dq[1].pop_back();
		}
		return to_vec(dq[0]);
	}
	else{
		deque<int> d0 = dq[0],d1 = dq[1];
		while(dq[1].size()>1){
			int mid = dq[1].size()>>1;
			deque<int> c;
			for(int i = 0;i<mid;i++)c.push_back(dq[1][i]);
			if(ask(dq[0],c))while(dq[1].size()>mid)dq[1].pop_back();
			else for(int i = 0;i<mid;i++)dq[1].pop_front();
		}
		while(dq[0].size()>1){
			int mid = dq[0].size()>>1;
			deque<int> c;
			for(int i = 0;i<mid;i++)c.push_back(dq[0][i]);
			if(ask(c,dq[1]))while(dq[0].size()>mid)dq[0].pop_back();
			else for(int i = 0;i<mid;i++)dq[0].pop_front();
		}
		assert(dq[0].size()==1&&dq[1].size() == 1);
		int a = dq[0][0],b = dq[1][0];
		dq[0] = d0,dq[1] = d1;
		while(dq[0][0] != a){
			dq[0].push_back(dq[0][0]);
			dq[0].pop_front();
		}
		while(dq[1][0] != b){
			dq[1].push_back(dq[1][0]);
			dq[1].pop_front();
		}
		while(!dq[1].empty()){
			dq[0].push_front(dq[1].front());
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:152:38: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  152 |    if(ask(dq[0],c))while(dq[1].size()>mid)dq[1].pop_back();
      |                          ~~~~~~~~~~~~^~~~
longesttrip.cpp:159:38: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  159 |    if(ask(c,dq[1]))while(dq[0].size()>mid)dq[0].pop_back();
      |                          ~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 11 ms 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 6 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 7 ms 600 KB Output is correct
4 Correct 7 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 11 ms 600 KB Output is correct
7 Correct 9 ms 600 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 6 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 5 ms 800 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 10 ms 600 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 6 ms 600 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 9 ms 600 KB Output is correct
15 Correct 8 ms 600 KB Output is correct
16 Correct 8 ms 796 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 9 ms 600 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 6 ms 856 KB Output is correct
22 Correct 6 ms 856 KB Output is correct
23 Correct 6 ms 600 KB Output is correct
24 Correct 6 ms 816 KB Output is correct
25 Correct 8 ms 600 KB Output is correct
26 Correct 10 ms 600 KB Output is correct
27 Correct 6 ms 600 KB Output is correct
28 Correct 6 ms 600 KB Output is correct
29 Correct 7 ms 600 KB Output is correct
30 Correct 4 ms 600 KB Output is correct
31 Correct 7 ms 600 KB Output is correct
32 Correct 7 ms 600 KB Output is correct
33 Correct 5 ms 600 KB Output is correct
34 Correct 8 ms 804 KB Output is correct
35 Correct 6 ms 600 KB Output is correct
36 Correct 8 ms 600 KB Output is correct
37 Correct 8 ms 600 KB Output is correct
38 Correct 6 ms 600 KB Output is correct
39 Correct 5 ms 812 KB Output is correct
40 Correct 7 ms 856 KB Output is correct
41 Correct 7 ms 808 KB Output is correct
42 Correct 7 ms 600 KB Output is correct
43 Correct 8 ms 604 KB Output is correct
44 Correct 6 ms 600 KB Output is correct
45 Correct 13 ms 600 KB Output is correct
46 Correct 10 ms 600 KB Output is correct
47 Correct 8 ms 600 KB Output is correct
48 Correct 8 ms 600 KB Output is correct
49 Correct 8 ms 600 KB Output is correct
50 Correct 6 ms 600 KB Output is correct
51 Correct 8 ms 856 KB Output is correct
52 Correct 9 ms 600 KB Output is correct
53 Correct 6 ms 600 KB Output is correct
54 Correct 6 ms 600 KB Output is correct
55 Correct 8 ms 804 KB Output is correct
56 Correct 8 ms 600 KB Output is correct
57 Correct 5 ms 600 KB Output is correct
58 Correct 7 ms 808 KB Output is correct
59 Correct 7 ms 600 KB Output is correct
60 Correct 9 ms 796 KB Output is correct
61 Correct 8 ms 600 KB Output is correct
62 Correct 8 ms 804 KB Output is correct
63 Correct 8 ms 812 KB Output is correct
64 Correct 6 ms 600 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 8 ms 600 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 15 ms 600 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 6 ms 804 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 8 ms 600 KB Output is correct
15 Correct 8 ms 600 KB Output is correct
16 Correct 8 ms 600 KB Output is correct
17 Correct 10 ms 600 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 8 ms 600 KB Output is correct
22 Correct 9 ms 600 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 7 ms 600 KB Output is correct
25 Correct 7 ms 600 KB Output is correct
26 Correct 6 ms 600 KB Output is correct
27 Correct 6 ms 600 KB Output is correct
28 Correct 8 ms 600 KB Output is correct
29 Correct 5 ms 600 KB Output is correct
30 Correct 6 ms 600 KB Output is correct
31 Correct 7 ms 856 KB Output is correct
32 Correct 10 ms 600 KB Output is correct
33 Correct 10 ms 600 KB Output is correct
34 Correct 9 ms 600 KB Output is correct
35 Correct 8 ms 600 KB Output is correct
36 Correct 8 ms 600 KB Output is correct
37 Correct 7 ms 600 KB Output is correct
38 Correct 8 ms 600 KB Output is correct
39 Correct 9 ms 600 KB Output is correct
40 Correct 6 ms 600 KB Output is correct
41 Correct 6 ms 600 KB Output is correct
42 Correct 6 ms 600 KB Output is correct
43 Correct 5 ms 600 KB Output is correct
44 Correct 4 ms 600 KB Output is correct
45 Correct 7 ms 808 KB Output is correct
46 Correct 6 ms 600 KB Output is correct
47 Correct 8 ms 600 KB Output is correct
48 Correct 8 ms 600 KB Output is correct
49 Correct 8 ms 816 KB Output is correct
50 Correct 7 ms 856 KB Output is correct
51 Correct 9 ms 600 KB Output is correct
52 Correct 8 ms 692 KB Output is correct
53 Correct 8 ms 600 KB Output is correct
54 Correct 7 ms 600 KB Output is correct
55 Correct 9 ms 600 KB Output is correct
56 Correct 7 ms 600 KB Output is correct
57 Correct 9 ms 600 KB Output is correct
58 Correct 7 ms 600 KB Output is correct
59 Correct 8 ms 600 KB Output is correct
60 Correct 8 ms 600 KB Output is correct
61 Correct 9 ms 600 KB Output is correct
62 Correct 5 ms 600 KB Output is correct
63 Correct 6 ms 600 KB Output is correct
64 Correct 7 ms 692 KB Output is correct
65 Correct 11 ms 600 KB Output is correct
66 Correct 7 ms 808 KB Output is correct
67 Correct 10 ms 600 KB Output is correct
68 Correct 7 ms 600 KB Output is correct
69 Correct 8 ms 600 KB Output is correct
70 Correct 8 ms 600 KB Output is correct
71 Correct 7 ms 600 KB Output is correct
72 Correct 6 ms 600 KB Output is correct
73 Correct 7 ms 812 KB Output is correct
74 Correct 12 ms 600 KB Output is correct
75 Correct 9 ms 600 KB Output is correct
76 Correct 8 ms 600 KB Output is correct
77 Correct 6 ms 816 KB Output is correct
78 Correct 7 ms 604 KB Output is correct
79 Correct 8 ms 600 KB Output is correct
80 Correct 8 ms 600 KB Output is correct
81 Correct 12 ms 808 KB Output is correct
82 Correct 10 ms 600 KB Output is correct