Submission #1190073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190073		hamzabc	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	5 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>


using namespace std;
#define all(x) x.begin(), x.end()


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){
        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{
            if (yl2.size() == 1){
                k = are_connected({ yl2.back() }, { yl1.back(), yl1.front() });
            }else if (yl1.size() == 1){
                k = are_connected({ yl2.back(), yl2.front() }, { yl1.back() });
            }else{
                k = are_connected({ yl2.back(), yl2.front() }, { yl1.back(), yl1.front() });
            }
            if (k == true){
                if (yl1.size() == 1){
                    for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
                }else{
                    if (yl2.size() == 1){
                        k = are_connected( { yl1.back() }, { yl2.back() } );
                    }else{
                        k = are_connected( { yl1.back() }, { yl2.back(), yl2.front() } );
                    }
                    if (k){
                        for (int i = 0; i < yl1.size(); i++) ret.push_back(yl1[i]);
                    }else{
                        for (int i = yl1.size() - 1; i >= 0; i--) ret.push_back(yl1[i]);
                    }
                }
                if (yl2.size() == 1){
                    for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
                }else{
                    if (yl1.size() == 1){
                        k = are_connected( { yl1.back() }, { yl2.back() } );
                    }else{
                        k = are_connected( { yl1.back(), yl1.front() }, { yl2.back() } );
                    }
                    if (k){
                        for (int i = 0; i < yl2.size(); i++) ret.push_back(yl2[i]);
                    }else{
                        for (int i = yl2.size() - 1; i >= 0; i--) ret.push_back(yl2[i]);
                    }
                }
                return ret;
            }
            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));
            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 != yl1.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;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:14:33: warning: narrowing conversion of 'nw' from 'long long int' to 'int' [-Wnarrowing]
   14 |         int k = are_connected({ nw }, { i });
      |                                 ^~
longesttrip.cpp:14:33: warning: narrowing conversion of 'nw' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:23:41: warning: narrowing conversion of 'nw' from 'long long int' to 'int' [-Wnarrowing]
   23 |                     k = are_connected({ nw }, { notret });
      |                                         ^~
longesttrip.cpp:23:41: warning: narrowing conversion of 'nw' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:23:49: warning: narrowing conversion of 'notret' from 'long long int' to 'int' [-Wnarrowing]
   23 |                     k = are_connected({ nw }, { notret });
      |                                                 ^~~~~~
longesttrip.cpp:23:49: warning: narrowing conversion of 'notret' from 'long long int' to 'int' [-Wnarrowing]

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60