oj.uz

Submission #861618

# Submission time Handle Problem Language Result Execution time Memory
861618 2023-10-16T15:02:09 Z faustaadp Longest Trip (IOI23_longesttrip) C++17
15 / 100
 730 ms 4396 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;
ll b[NN], n, ada = 0;
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 " << n << "\n";
    if(ret.size() == n)ada = 1;
    if(ada)return;
    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();
}
std::vector<int> longest_trip(int N, int D)
{
    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++)
        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:19: 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() == n)ada = 1;
      |        ~~~~~~~~~~~^~~~
longesttrip.cpp:19: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]
   19 |     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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2648 KB Output is correct
2 Correct 21 ms 2648 KB Output is correct
3 Correct 108 ms 3416 KB Output is correct
4 Correct 329 ms 3680 KB Output is correct
5 Correct 723 ms 4152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2772 KB Output is correct
2 Correct 20 ms 2648 KB Output is correct
3 Correct 120 ms 2904 KB Output is correct
4 Correct 375 ms 3300 KB Output is correct
5 Correct 712 ms 4396 KB Output is correct
6 Correct 7 ms 2648 KB Output is correct
7 Correct 23 ms 2648 KB Output is correct
8 Correct 114 ms 2904 KB Output is correct
9 Correct 250 ms 3300 KB Output is correct
10 Correct 700 ms 4184 KB Output is correct
11 Correct 728 ms 4008 KB Output is correct
12 Correct 721 ms 3552 KB Output is correct
13 Correct 668 ms 4164 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2648 KB Output is correct
2 Correct 21 ms 2648 KB Output is correct
3 Correct 115 ms 3568 KB Output is correct
4 Correct 324 ms 3484 KB Output is correct
5 Correct 720 ms 3484 KB Output is correct
6 Correct 6 ms 2648 KB Output is correct
7 Correct 26 ms 2648 KB Output is correct
8 Correct 121 ms 2924 KB Output is correct
9 Correct 252 ms 3344 KB Output is correct
10 Correct 699 ms 4176 KB Output is correct
11 Correct 700 ms 3996 KB Output is correct
12 Correct 713 ms 4288 KB Output is correct
13 Correct 713 ms 4028 KB Output is correct
14 Incorrect 1 ms 2648 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2648 KB Output is correct
2 Correct 25 ms 2648 KB Output is correct
3 Partially correct 113 ms 3160 KB Output is partially correct
4 Partially correct 338 ms 3328 KB Output is partially correct
5 Partially correct 694 ms 4040 KB Output is partially correct
6 Correct 8 ms 2648 KB Output is correct
7 Correct 27 ms 2648 KB Output is correct
8 Partially correct 116 ms 2908 KB Output is partially correct
9 Partially correct 274 ms 3332 KB Output is partially correct
10 Partially correct 699 ms 3928 KB Output is partially correct
11 Partially correct 730 ms 4048 KB Output is partially correct
12 Partially correct 717 ms 3744 KB Output is partially correct
13 Partially correct 699 ms 4120 KB Output is partially correct
14 Incorrect 1 ms 2648 KB Incorrect
15 Halted 0 ms 0 KB -