제출 #1240954

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

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

int c[257][257];
int sor(int a,int b) {
    if (c[a][b] != -1) return c[a][b];
    if (c[b][a] != -1) return c[b][a];
    if (a == b) return 0;
    return c[a][b] = are_connected({a},{b});
}

int sor(vi v1,vi v2) {
    if (v1.empty()  || v2.empty()) return 0;
    return are_connected(v1,v2);
}
std::vector<int> longest_trip(int N, int D)
{  
    memset(c,-1,sizeof c);
    vi perm(N);
    iota(all(perm),0ll);
    shuffle(all(perm),mt19937());
    vi path,path2;
    path.push_back(perm[0]);
    for (int i=1;i<N;i++) {
        if (sor(path.back(),perm[i])) {
            path.push_back(perm[i]);
        }else {
            if (path2.empty() || sor(path2.back(),perm[i])) {
                path2.push_back(perm[i]);
            }else {
                for (auto it : path2) path.push_back(it);
                path2.clear();
                path2.push_back(perm[i]);
            }
        }
    }
    assert(!path.empty());
    if (!path2.empty() && sor(path,path2)) {
        vi uc1 = {path.front(),path.back()};
        vi uc2 = {path2.front(),path2.back()}; 
        if (sor(uc1[0],uc2[0])) {
            reverse(all(path));
            for (auto it : path2) path.push_back(it);
            return path;
        }
        else if (big(uc2) > 1 && sor(uc1[0],uc2[1])) {
            reverse(all(path));
            reverse(all(path2));
            for (auto it : path2) path.push_back(it);
            return path;
        }
        else if (big(uc1) > 1 && sor(uc1[1],uc2[0])) {
            for (auto it : path2) path.push_back(it);
            return path;
        }
        else {
            reverse(all(path2));
            for (auto it : path2) path.push_back(it);
            return path;
        }
        assert(0);
        //ikisi de cycle (bs)
        int l = 1;
        int r = path.size();
        while (l<=r) {
            int m = (l+r) >> 1;
            vi v;
            for (int j = 0;j<m;j++) v.push_back(path[j]);
            if (sor(v,path2)) r = m-1;
            else l = m+1;
        }
        int p1 = l;
        assert(sor({path[p1-1]},path2));
        l = 1;
        r = path2.size();
        while (l<=r) {
            int m = (l+r) >> 1;
            vi v;
            for (int j = 0;j<m;j++) v.push_back(path2[j]);
            if (sor(v,vi{path[p1-1]})) r = m-1;
            else l = m+1;
        }
        int p2 = l;
        vi ans;
        for (int j = p1;j<path.size();j++) ans.push_back(path[j]);
        for (int j = 0;j<p1;j++) ans.push_back(path[j]);
        for (int j = p2-1;j<path2.size();j++) ans.push_back(path2[j]);
        for (int j = 0;j<p2-1;j++) ans.push_back(path2[j]);
        return ans; 
    }
    else {
        if (path.size() >= path2.size()) return path;
        return path2;
    }
}

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