oj.uz

Submission #861622

# Submission time Handle Problem Language Result Execution time Memory
861622 2023-10-16T15:09:59 Z faustaadp Longest Trip (IOI23_longesttrip) C++17
0 / 100
 1000 ms 4312 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;
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";
    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] = 1;
    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)
{
    mxx = 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])
        {
            now = 0;
            dfs2(i);
        }
    // cout << mxx << "_\n";
    for(ll i = 0; i < N; i++)
    {
        b[i] = 0;
    }
    for(ll i = 0; i < N; i++)
        dfs(i);
    return ret;
    // 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:17: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]
   17 |     if(ret.size() * 2 >= mxx)ada = 1;
      |        ~~~~~~~~~~~~~~~^~~~~~
longesttrip.cpp:20: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]
   20 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
longesttrip.cpp: In function 'void dfs2(ll)':
longesttrip.cpp:34: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]
   34 |     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 2648 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2648 KB Output is correct
2 Correct 21 ms 2724 KB Output is correct
3 Correct 119 ms 2904 KB Output is correct
4 Correct 361 ms 3588 KB Output is correct
5 Correct 699 ms 4200 KB Output is correct
6 Correct 8 ms 2648 KB Output is correct
7 Correct 19 ms 2648 KB Output is correct
8 Correct 107 ms 3416 KB Output is correct
9 Correct 253 ms 3672 KB Output is correct
10 Correct 664 ms 4312 KB Output is correct
11 Correct 678 ms 4116 KB Output is correct
12 Correct 711 ms 3936 KB Output is correct
13 Correct 685 ms 3928 KB Output is correct
14 Correct 9 ms 2904 KB Output is correct
15 Correct 11 ms 2648 KB Output is correct
16 Correct 36 ms 2648 KB Output is correct
17 Correct 66 ms 2648 KB Output is correct
18 Correct 106 ms 3160 KB Output is correct
19 Correct 231 ms 3168 KB Output is correct
20 Correct 231 ms 3164 KB Output is correct
21 Correct 714 ms 4184 KB Output is correct
22 Correct 699 ms 4272 KB Output is correct
23 Correct 691 ms 3940 KB Output is correct
24 Correct 673 ms 3932 KB Output is correct
25 Correct 10 ms 2648 KB Output is correct
26 Correct 8 ms 2648 KB Output is correct
27 Correct 25 ms 2648 KB Output is correct
28 Correct 25 ms 2880 KB Output is correct
29 Correct 20 ms 2900 KB Output is correct
30 Correct 169 ms 3304 KB Output is correct
31 Execution timed out 3100 ms 3064 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

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