Submission #1112592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112592		tibinyte	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	1142 ms	1360 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

const string asafaciunstringsus = R""""(
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
)"""";

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random(int st, int dr)
{
    uniform_int_distribution<int> dist(st, dr);
    return dist(rng);
}

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator*(Mint oth)
    {
        return 1ll * val * oth.val;
    }
    void operator+=(Mint oth)
    {
        val = (*this + oth).val;
    }
    void operator-=(Mint oth)
    {
        val = (*this - oth).val;
    }
    void operator*=(Mint oth)
    {
        val = (*this * oth).val;
    }
};

Mint powmod(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 1)
    {
        return powmod(a, b - 1) * a;
    }
    Mint p = powmod(a, b / 2);
    return p * p;
}

/*
                 .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/
vector<vector<int>> mat;

bool get(int i, int j)
{
    if (mat[i][j] == -1)
    {
        mat[i][j] = mat[j][i] = are_connected({i}, {j});
    }
    return mat[i][j];
}

std::vector<int> longest_trip(int N, int D)
{
    int n = N;
    mat = vector<vector<int>>(n, vector<int>(n, -1));
    vector<bool> vis(n);
    vector<int> ord;
    function<void(int)> dfs = [&](int node)
    {
        ord.push_back(node);
        vis[node] = true;
        for (int i = 0; i < n; ++i)
        {
            if (!vis[i] && get(node, i))
            {
                dfs(i);
            }
        }
    };
    function<vector<int>(vector<int>)> build = [&](vector<int> ord)
    {
        if (ord.size() <= 2)
        {
            return ord;
        }
        vector<int> ans;
        ans.push_back(ord[0]);
        ans.push_back(ord[1]);
        for (int lol = 2; lol < ord.size(); ++lol)
        {
            int it = ord[lol];
            if (get(ans.back(), it))
            {
                ans.push_back(it);
                continue;
            }
            if (get(ans.front(), it))
            {
                ans.insert(ans.begin(), it);
                continue;
            }
            for (int i = 0; i < ans.size(); ++i)
            {
                int node = ans[i];
                if (get(node, it))
                {
                    vector<int> new_ans(ans.size() + 1);
                    int p = 0;
                    new_ans[p++] = it;
                    for (int j = i; j >= 0; --j)
                    {
                        new_ans[p++] = ans[j];
                    }
                    for (int j = ans.size() - 1; j > i; --j)
                    {
                        new_ans[p++] = ans[j];
                    }
                    ans = new_ans;
                    break;
                }
            }
        }
        return ans;
    };
    vector<int> ans;
    for (int i = 0; i < n; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
            if (ord.size() > ans.size())
            {
                ans = build(ord);
            }
            ord.clear();
        }
    }
    return ans;
}

/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before

Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/

Compilation message (stderr)

longesttrip.cpp: In lambda function:
longesttrip.cpp:127:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int lol = 2; lol < ord.size(); ++lol)
      |                           ~~~~^~~~~~~~~~~~
longesttrip.cpp:140:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for (int i = 0; i < ans.size(); ++i)
      |                             ~~^~~~~~~~~~~~

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