#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int mxn = 300;
int ask(vector<int> a,vector<int> b){
/*
cerr<<"ASK: ";
for(auto i:a)cerr<<i<<',';cerr<<endl;
for(auto i:b)cerr<<i<<',';cerr<<endl;
*/
return are_connected(a,b);
}
int dp[mxn][mxn];
bitset<mxn> vis;
int N;
int ask(int a,int b){
if(dp[a][b] != -1)return dp[a][b];
return ask(vector<int>({a}),vector<int>({b}));
}
int ask(deque<int> a,int b){
vi v;
for(auto &i:a)v.push_back(i);
return ask(v,vi({b}));
}
void dfs(int now){
vis[now] = true;
for(int i = 0;i<N;i++){
if(ask(now,i)&&!vis[i])dfs(i);
}
return;
}
vector<int> get_max_cc(){
//cerr<<"GETTING MAX CC: "<<endl;
vector<int> heads;
vis.reset();
for(int i = 0;i<N;i++){
if(!vis[i]){
heads.push_back(i);
dfs(i);
}
}
int ans = 0,tar = -1;
for(auto &i:heads){
vis.reset();
dfs(i);
if(vis.count()>ans){
ans = vis.count();
tar = i;
}
}
assert(tar != -1);
dfs(tar);
vector<int> re;
for(int i = 0;i<N;i++)if(vis[i])re.push_back(i);
return re;
}
std::vector<int> longest_trip(int NN, int D){
N = NN;
memset(dp,-1,sizeof(dp));
vis.reset();
dfs(1);
if(vis.count() != N){
return get_max_cc();
}
deque<int> dq[2];
set<int> st;
for(int i = 0;i<N;i++)st.insert(i);
if(ask(0,1))dq[0] = {0,1};
else if(ask(1,2))dq[0] = {1,2};
else dq[0] = {0,2};
for(auto &i:dq[0])st.erase(i);
while(st.size()){
if(dq[0].size()<dq[1].size())dq[0].swap(dq[1]);
//cerr<<*st.begin()<<endl;
auto now = *st.begin();
st.erase(now);
if(ask(now,dq[0].back())){
dq[0].push_back(now);
dq[0].swap(dq[1]);
}
else{
dq[1].push_back(now);
}
if(dq[0].empty()||dq[1].empty())continue;
int s = dq[0].front(),t = dq[0].back();
if(!ask(s,t)){
if(ask(s,now)){
while(!dq[1].empty()){
dq[0].push_front(dq[1].back());
dq[1].pop_back();
}
}
else if(ask(t,now)){
while(!dq[1].empty()){
dq[0].push_back(dq[1].back());
dq[1].pop_back();
}
}
}
else{
int tar = -1;
deque<int> c = dq[0];
while(c.size()>1){
int mid = c.size()>>1;
deque<int> tmp;
for(int i = 0;i<mid;i++)tmp.push_back(c[i]);
if(ask(tmp,now)){
int s = c.size();
for(int i = mid;i<s;i++)c.pop_back();
}
else{
for(int i = 0;i<mid;i++)c.pop_front();
}
}
//cerr<<now<<":"<<c.size()<<' '<<c[0]<<endl;
if(c.size()&&!ask(c,now))c.clear();
if(c.size())tar = c[0];
if(tar == -1)continue;
assert(c.size() == 1);
while(dq[0][0] != tar){
dq[0].push_back(dq[0][0]);
dq[0].pop_front();
}
while(!dq[1].empty()){
dq[0].push_front(dq[1].back());
dq[1].pop_back();
}
}
}
if(dq[0].size()<dq[1].size())dq[0].swap(dq[1]);
/*
cerr<<"DQ: "<<endl;
for(auto &i:dq[0])cerr<<i<<' ';cerr<<endl;
for(auto &i:dq[1])cerr<<i<<' ';cerr<<endl;
cerr<<endl;
*/
vector<int> ans;
for(auto &i:dq[0])ans.push_back(i);
return ans;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> get_max_cc()':
longesttrip.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if(vis.count()>ans){
| ~~~~~~~~~~~^~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:72:17: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if(vis.count() != N){
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
