제출 #1190036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190036		hamzabc	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	4 ms	416 KiB

longesttrip

#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 != 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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