제출 #853975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853975		FairyWinx	가장 긴 여행 (IOI23_longesttrip)	C++17	40 / 100	19 ms	856 KiB

longesttrip

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

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

// #ifdef LOCAL
// vector<vector<int>> G_secret;
// int n;

// bool are_connected(vector<int> a, vector<int> b) {
//     for (int i : a) {
//         for (int j : b) {
//             if (G_secret[i][j])
//                 return true;
//         }
//     }
//     return false;
// }
// #endif


#ifdef LOCAL

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    ++call_counter;
    ++total_call_counter;
    if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
    {
        protocol_violation("too many calls");
    }

    int nA = A.size(), nB = B.size();
    landmark_counter += nA + nB;
    if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
    {
        protocol_violation("too many elements");
    }

    if (nA == 0 || nB == 0)
    {
        protocol_violation("invalid array");
    }
    for (int i = 0; i < nA; ++i)
    {
        if (A[i] < 0 || N <= A[i])
        {
            protocol_violation("invalid array");
        }
        if (present[A[i]])
        {
            protocol_violation("invalid array");
        }
        present[A[i]] = true;
    }
    for (int i = 0; i < nA; ++i)
    {
        present[A[i]] = false;
    }
    for (int i = 0; i < nB; ++i)
    {
        if (B[i] < 0 || N <= B[i])
        {
            protocol_violation("invalid array");
        }
        if (present[B[i]])
        {
            protocol_violation("invalid array");
        }
        present[B[i]] = true;
    }
    for (int i = 0; i < nB; ++i)
    {
        present[B[i]] = false;
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (A[i] == B[j])
            {
                protocol_violation("non-disjoint arrays");
            }
        }
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
            {
                return true;
            }
        }
    }

    return false;
}

#endif


struct dsu {
    vector<int> p;

    dsu(int n) {
        p.resize(n);
        iota(all(p), 0);
    }

    int get(int a) {
        if (p[a] == a)
            return a;
        return p[a] = get(p[a]);
    }

    void merge(int a, int b) {
        a = get(a), b = get(b);
        p[a] = b;
    }
};

vector<int> get_comp(int n, int v, dsu &d) {
    vector<int> comp;
    for (int i = 0; i < n; ++i) {
        if (d.get(i) == v) {
            comp.push_back(i);
        }
    }
    return comp;
}

void add_comp(vector<int> &ans, vector<int> &comp, pair<int, int> end) {
    ans.push_back(end.first);
    for (int j : comp) {
        if (j != end.first && j != end.second) {
            ans.push_back(j);
        }
    }
    if (end.first != end.second) {
        ans.push_back(end.second);
    }
}

vector<int> longest_trip(int n, int D) { // Случай, когда отдельная вершинка - 0
    dsu d(n);
    vector<vector<int>> path;
    vector<pair<int, int>> ends;
    ends.push_back({0, 0});
    path.push_back({0});
    vector<int> ost(n - 1);
    iota(all(ost), 1);
    while (true) {
        int ind_comp = ost[0];
        bool find = false;
        bool was_merge = false;
        for (int i = 0; i < (int) ost.size(); ++i) {
            if (are_connected({ends.back().second}, get_comp(n, ost[i], d))) {
                path.push_back(get_comp(n, ost[i], d));
                int last_end = ends.back().second;
                ends.emplace_back();
                for (int i : path.back()) { // поиск вершины.
                    if (are_connected({last_end}, {i})) {
                        ends.back().first = i;
                    }
                }
                if (path.back().size() == 1) {
                    ends.back().second = ends.back().first;
                } else {
                    if (ends.back().first != path.back()[0]) {
                        ends.back().second = path.back()[0];
                    } else {
                        ends.back().second = path.back().back();
                    }
                }
                swap(ost[i], ost.back());
                ost.pop_back();
                find = true;
                break;
            } else {
                was_merge = true;
                d.merge(ost[i], ind_comp);
                swap(ost[i], ost.back());
                ost.pop_back();
                --i;
            }
        }
        if (was_merge)
            ost.push_back(ind_comp);
        if (!ost.size()) {
            vector<int> ans;
            for (int i = 0; i < (int) path.size(); ++i) {
                add_comp(ans, path[i], ends[i]);
            }
            // cout << "MEOW1\n";
            return ans;
        }
        if (!find) {
            vector<int> last_comp = get_comp(n, ost[0], d);
            for (int i = 0; i < (int) path.size(); ++i) {
                if (are_connected({last_comp[0]}, {ends[i].first})) {
                    vector<int> ans;
                    for (int j : last_comp) {
                        if (j != last_comp[0]) {
                            ans.push_back(j);
                        }
                    }
                    ans.push_back(last_comp[0]);
                    for (int j = i; j < (int) path.size(); ++j) {
                        add_comp(ans, path[j], ends[j]);
                    }
                    for (int j = 0; j < i; ++j) {
                        add_comp(ans, path[j], ends[j]);
                    }
                    // cout << "MEOW2\n";
                    return ans;
                }
            }
            vector<int> ans;
            if (last_comp.size() > n - last_comp.size()) {
                for (int i : last_comp)
                    ans.push_back(i);
            } else {
                for (auto i : path) {
                    for (int j : i)
                        ans.push_back(j);
                }
            }
            return ans;
        }
    }
    assert(0);
    return {-1};
}

#ifdef LOCAL

int main()
{
    assert(1 == scanf("%d", &C));
    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        call_counter = 0;
        assert(2 == scanf("%d %d", &N, &D));

        present.assign(N, false);
        U.resize(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        for (int i = 2; i < N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (U[i][j] + U[i][k] + U[j][k] < D)
                    {
                        printf("Insufficient Density\n");
                        exit(0);
                    }
                }
            }
        }

        std::vector<int> t = longest_trip(N, D);
        int l = t.size();
        printf("%d\n", l);
        for (int i = 0; i < l; ++i)
        {
            printf(i == 0 ? "%d" : " %d", t[i]);
        }
        printf("\n");
        // printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    // printf("%d\n", maximumCalls);

    return 0;
}

#endif

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