oj.uz

답안 #1112572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112572 2024-11-14T10:57:50 Z tibinyte 가장 긴 여행 (IOI23_longesttrip) C++17
0 / 100
 1000 ms 508 KB 
#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  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

std::vector<int> longest_trip(int N, int D)
{
    int n = N;
    vector<vector<bool>> mat(n, vector<bool>(n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (are_connected({i}, {j}))
            {
                mat[i][j] = mat[j][i] = 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] && mat[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 (mat[ans.back()][it])
            {
                ans.push_back(it);
                continue;
            }
            if (mat[ans.front()][it])
            {
                ans.insert(ans.begin(), it);
                continue;
            }
            assert(mat[ans.front()][ans.back()]); // we have a cycle
            for (int i = 0; i < ans.size(); ++i)
            {
                int node = ans[i];
                if (mat[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 = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            dfs(i);
            vector<int> lesgo = build(ord);
            if (lesgo.size() > ans.size())
            {
                ans = lesgo;
            }
            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

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:141:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for (int i = 0; i < ans.size(); ++i)
      |                             ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 615 ms 456 KB Output is correct

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 336 KB Output is correct
2 Correct 73 ms 336 KB Output is correct
3 Correct 436 ms 336 KB Output is correct
4 Execution timed out 1189 ms 444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 336 KB Output is correct
2 Correct 69 ms 508 KB Output is correct
3 Correct 368 ms 336 KB Output is correct
4 Execution timed out 1090 ms 440 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 336 KB Output is correct
2 Correct 89 ms 336 KB Output is correct
3 Correct 432 ms 504 KB Output is correct
4 Execution timed out 1194 ms 436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 336 KB Output is correct
2 Correct 83 ms 336 KB Output is correct
3 Partially correct 442 ms 336 KB Output is partially correct
4 Execution timed out 1167 ms 440 KB Time limit exceeded
5 Halted 0 ms 0 KB -