oj.uz

Submission #861634

# Submission time Handle Problem Language Result Execution time Memory
861634 2023-10-16T15:24:57 Z faustaadp Longest Trip (IOI23_longesttrip) C++17
0 / 100
 852 ms 5256 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define pb push_back
const ll NN = 1e5 + 5;
vector<int> ret, ret2;
ll b[NN], n, ada = 0, mxx, now, coba = 0, ti;
vector<ll> v[NN];
void dfs(ll pos)
{
    if(ada)return ;
    b[pos] = 1;
    ret.pb(pos);
    // cout << pos << " mas " << ret.size() << "_\n";
    // cout << ret.size() << " dan " << mxx << "\n";
    coba++;
    if(ret2.size() < ret.size())ret2 = ret;
    if(coba >= 100000)ada = 2;
    if(ret.size() * 2 >= mxx)ada = 1;
    if(ada)return;
    // random_shuffle(v[pos].begin(), v[pos].end());
    for(ll i = 0; i < v[pos].size(); i++)
    {
        if(b[v[pos][i]] == 0)dfs(v[pos][i]);
        if(ada)return ;
    }
    b[pos] = 0;
    // cout << pos << " kel\n";
    ret.pop_back();
}
void dfs2(ll pos)
{
    now++;
    mxx = max(mxx, now);
    b[pos] = ti;
    for(ll i = 0; i < v[pos].size(); i++)
        if(b[v[pos][i]] == 0)
            dfs2(v[pos][i]);
}
std::vector<int> longest_trip(int N, int D)
{
    ret2.clear();
    mxx = 0;
    coba = 0;
    ada = 0;
    n = N;
    ret.clear();
    for(ll i = 0; i < N; i++)
    {
        v[i].clear();
        b[i] = 0;
    }
    for(ll i = 0; i < N; i++)
        for(ll j = i + 1; j < N; j++)
        {
            vector<int> A;A.pb(i);
            vector<int> B;B.pb(j);
            bool isi = are_connected(A, B);
            if(isi)
            {
                // cout << i << "--" << j << "\n";
                v[i].pb(j);
                v[j].pb(i);
            }
        }
    for(ll i = 0; i < N; i++)
        if(!b[i])
        {
            ti++;
            now = 0;
            dfs2(i);
        }
    for(ll i = 0; i < N; i++)
    {
        b[i] = 0;
    }
    ti = 1;
    vector<ll> cal;
    for(ll i = 0; i < N; i++)
        if(!b[i])
        {
            ti++;
            now = 0;
            dfs2(i);
            if(now != mxx)
                continue;
            for(ll j = 0; j < N; j++)
            {
                if(b[j] == ti)
                    cal.pb(j);
            }
            break;
        }
    memset(b, 0, sizeof(b));
    for(auto aa : cal)
    {
        dfs(aa);
        if(ada == 2)
            ada = 0;
    }
    return ret2;
    // ll mul = 1;
    // if(N % 2 == 0)
    // {
    //     vector<int> A;A.pb(0);
    //     vector<int> B;B.pb(1);
    //     bool isi = are_connected(A, B);
    //     if(!isi)
    //         swap(cal[1], cal[2]);
    //     ret.pb(cal[0]);
    //     ret.pb(cal[1]);
    // }
    // else
    //     ret.pb(cal[0]);
    // for(ll i = mul; i + 1 < N; i += 2)
    // {
    //     ll now = ret.back();
    //     vector<int> A;A.pb(now);
    //     vector<int> B;A.pb(cal[i]);
    //     bool isi = are_connected(A, B);
    //     if()
    // }
    // return ret;
}

Compilation message

longesttrip.cpp: In function 'void dfs(ll)':
longesttrip.cpp:20:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   20 |     if(ret.size() * 2 >= mxx)ada = 1;
      |        ~~~~~~~~~~~~~~~^~~~~~
longesttrip.cpp:23:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
longesttrip.cpp: In function 'void dfs2(ll)':
longesttrip.cpp:37:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3416 KB Output is correct
2 Correct 26 ms 3416 KB Output is correct
3 Correct 140 ms 4356 KB Output is correct
4 Correct 332 ms 3684 KB Output is correct
5 Correct 722 ms 4344 KB Output is correct
6 Correct 13 ms 3416 KB Output is correct
7 Correct 21 ms 3416 KB Output is correct
8 Correct 127 ms 3672 KB Output is correct
9 Correct 262 ms 4080 KB Output is correct
10 Correct 733 ms 4372 KB Output is correct
11 Correct 729 ms 4500 KB Output is correct
12 Correct 694 ms 4824 KB Output is correct
13 Correct 701 ms 4360 KB Output is correct
14 Correct 14 ms 3416 KB Output is correct
15 Correct 17 ms 3416 KB Output is correct
16 Correct 34 ms 3416 KB Output is correct
17 Correct 66 ms 3672 KB Output is correct
18 Correct 115 ms 4184 KB Output is correct
19 Correct 281 ms 4216 KB Output is correct
20 Correct 264 ms 3928 KB Output is correct
21 Correct 753 ms 4424 KB Output is correct
22 Correct 724 ms 4888 KB Output is correct
23 Correct 735 ms 4876 KB Output is correct
24 Correct 680 ms 4440 KB Output is correct
25 Correct 14 ms 3416 KB Output is correct
26 Correct 13 ms 3416 KB Output is correct
27 Correct 22 ms 3416 KB Output is correct
28 Correct 21 ms 3416 KB Output is correct
29 Correct 24 ms 3416 KB Output is correct
30 Correct 157 ms 4336 KB Output is correct
31 Correct 160 ms 4440 KB Output is correct
32 Correct 154 ms 3416 KB Output is correct
33 Correct 248 ms 4124 KB Output is correct
34 Correct 268 ms 3920 KB Output is correct
35 Correct 238 ms 3844 KB Output is correct
36 Correct 678 ms 4084 KB Output is correct
37 Correct 776 ms 4100 KB Output is correct
38 Correct 796 ms 5256 KB Output is correct
39 Correct 782 ms 4836 KB Output is correct
40 Correct 826 ms 5076 KB Output is correct
41 Correct 852 ms 4028 KB Output is correct
42 Correct 816 ms 4948 KB Output is correct
43 Correct 799 ms 5060 KB Output is correct
44 Correct 733 ms 4980 KB Output is correct
45 Correct 14 ms 3672 KB Output is correct
46 Correct 15 ms 3416 KB Output is correct
47 Correct 27 ms 3672 KB Output is correct
48 Correct 29 ms 3672 KB Output is correct
49 Correct 28 ms 3672 KB Output is correct
50 Correct 220 ms 4192 KB Output is correct
51 Incorrect 16 ms 3840 KB Incorrect
52 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3924 KB Incorrect
2 Halted 0 ms 0 KB -