| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1190034 | hamzabc | 가장 긴 여행 (IOI23_longesttrip) | C++20 | 0 ms | 0 KiB |
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
std::vector<int> longest_trip(int N, int D)
{
vector<int> prv(N, -1), nxt(N, -1);
long long int notret = -1, notb = -1, b = 0, nw = 0;
bool flag = false;
for (int i = 1; i < N; i++){
int k = are_connected({ nw }, { i });
if (k == false){
if (notret == -1){
notret = i;
notb = i;
}else{
if (flag){
k = false;
}else{
k = are_connected({ nw }, { notret });
}
if (k == false){
prv[notret] = i;
nxt[i] = notret;
notret = i;
flag = true;
}else{
nxt[nw] = notret;
prv[notret] = nw;
nw = notb;
notb = i;
notret = i;
}
}
}else{
nxt[nw] = i;
prv[i] = nw;
nw = i;
flag = false;
}
}
vector<int> ret;
if (notret == -1){
cerr << "dvm";
for (int i = b; i != -1; i = nxt[i]) ret.push_back(i);
}else{
swap(notb, notret);
vector<int> yl1, yl2;
for (int i = b; i != -1; i = nxt[i]) yl1.push_back(i);
for (int i = notb; i != -1; i = nxt[i]) yl2.push_back(i);
int k = are_connected(yl1, yl2);
if (k == false){
if (yl1.size() > yl2.size()){
ret = yl1;
}else{
ret = yl2;
}
}else{
vector<int> src;
int add = 0, add2 = 0;
reverse(all(yl1));
for (int i = ceil(log2(yl1.size())) - 1; i >= 0; i--){
i = min(i, (int)ceil(log2(yl1.size() - add)) - 1);
src.clear();
for (int o = 0; o < (1LL << i); o++){
src.push_back(yl1[o + add]);
}
k = are_connected(src, yl2);
if (k == false){
add += (1LL << i);
}
}
add = yl1.size() - 1 - add;
reverse(all(yl1));
k = are_connected({ yl2[yl2.size() - 1] }, { yl1[add] });
if (k == true){
if (add != yl1.size() - 1){
prv[b] = nw;
nxt[nw] = b;
b = nxt[yl1[add]];
prv[b] = -1;
nxt[yl1[add]] = -1;
}
for (int i = b; i != -1; i = nxt[i]) ret.push_back(i);
for (int i = yl2.size() - 1; i >= 0; i--) ret.push_back(yl2[i]);
return ret;
}
for (int i = ceil(log2(yl2.size() - 1)) - 1; i >= 0; i--){
i = min(i, (int)ceil(log2(yl2.size() - add2 - 1)) - 1);
src.clear();
for (int o = 0; o < (1LL << i); o++){
src.push_back(yl2[o + add2]);
}
k = are_connected(src, { yl1[add] });
if (k == false){
add2 += (1LL << i);
prv[notb] = notret;
nxt[notret] = notb;
}
}
if (add != y1.size() - 1){
prv[b] = nw;
nxt[nw] = b;
b = nxt[yl1[add]];
prv[nxt[yl1[add]]] = -1;
}
if (add2){
nxt[prv[yl2[add2]]] = -1;
}
nxt[yl1[add]] = yl2[add2];
prv[yl2[add2]] = yl1[add];
ret.clear();
for (int i = b; i != -1; i = nxt[i]) ret.push_back(i);
}
}
return ret;
}