Submission #1091234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091234		Zanite	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	383 ms	69504 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

struct Solver {
    int n, d;
    vector<vector<int>> adj;
    vector<vector<vector<int>>> unknown;

    Solver(int n, int d) :
        n(n), d(d),
        adj(n, vector(n, -1)), unknown(n, vector(n, vector(n, 3)))
    {}

    int query(int u, int v) { return are_connected({u}, {v}); }

    void set(int u, int v, int x) {
        adj[u][v] = x;
        for (int i = 0; i < u; i++) relax(i, u, v);
        for (int i = u+1; i < v; i++) relax(u, i, v);
        for (int i = v+1; i < n; i++) relax(u, v, i);
    }

    void relax(int u, int v, int w) {
        unknown[u][v][w]--;
        if (unknown[u][v][w] == 1) {
            int total = 0;
            if (adj[u][v] == -1) total += adj[u][v];
            if (adj[u][w] == -1) total += adj[u][w];
            if (adj[v][w] == -1) total += adj[v][w];

            int rem = 2 - total;
            if (adj[u][v] == -1) set(u, v, rem);
            if (adj[u][w] == -1) set(u, w, rem);
            if (adj[v][w] == -1) set(v, w, rem);
        }
    }

    void dfs(int cur, vector<bool> &vis, vector<int> &cur_stk, vector<int> &ans) {
        cur_stk.push_back(cur);
        vis[cur] = true;

        if (cur_stk.size() > ans.size()){
            ans = vector<int>(cur_stk);
        }

        for (int i = 0; i < n; i++) if (adj[cur][i] && !vis[i]) {
            dfs(i, vis, cur_stk, ans);
        }

        cur_stk.pop_back();
    }

    vector<int> solve() {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (adj[i][j] == -1) set(i, j, query(i, j));
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) adj[i][j] = 0;
                else if (adj[i][j] == -1) adj[i][j] = adj[j][i];
            }
        }

        vector<int> ret = {};
        for (int root = 0; root < n; root++) {
            vector<int> cur = {};
            vector<bool> vis(n, false);
            dfs(root, vis, cur, ret);
        }

        return ret;
    }
};

vector<int> longest_trip(int N, int D) {
    Solver solver(N, D);
    return solver.solve();
}

#ifdef Zanite

#include "longesttrip.h"

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

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: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60