oj.uz

Submission #1030066

# Submission time Handle Problem Language Result Execution time Memory
1030066 2024-07-21T19:01:13 Z mindiyak Longest Trip (IOI23_longesttrip) C++17
40 / 100
 878 ms 1496 KB 
#include "longesttrip.h"
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;

vvi paths;
vi visited;
vi cur_path;
int node,dis;

void dfs(int pos,int height,vi cur){
    if(visited[pos])return;
    cur.pb(pos);
    visited[pos] = 1;
    if(dis < height){
        dis = height;
        node = pos;
        cur_path = cur;
    }
    for(int a:paths[pos]){
        dfs(a,height+1,cur);
    }
}

vi longest_trip(int N, int D)
{
    paths = vvi(N);
    FOR(i,0,N){
        FOR(j,i+1,N){
            if(are_connected({i},{j})){
                paths[i].pb(j);
                paths[j].pb(i);
            }
        }
    }

    visited = vi(N,0);
    vi possibles;

    FOR(i,0,N){
        if(visited[i])continue;
        node = -1;
        dis = -1;
        vi cur;
        dfs(i,1,cur);
        if(node != -1)possibles.pb(node);
    }

    visited = vi(N,0);
    int temp = -1;
    vi ans;
    cur_path = vi();

    for(int i:possibles){
        node = -1;
        dis = -1;
        vi cur;
        dfs(i,1,cur);
        if(temp < dis){
            temp = dis;
            ans = cur_path;
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 210 ms 988 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 157 ms 600 KB Output is correct
4 Correct 439 ms 724 KB Output is correct
5 Correct 849 ms 1292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 137 ms 344 KB Output is correct
4 Correct 425 ms 696 KB Output is correct
5 Correct 849 ms 1316 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 171 ms 692 KB Output is correct
9 Correct 358 ms 704 KB Output is correct
10 Correct 860 ms 1036 KB Output is correct
11 Correct 854 ms 1072 KB Output is correct
12 Correct 851 ms 1136 KB Output is correct
13 Correct 856 ms 1368 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 135 ms 452 KB Output is correct
4 Correct 390 ms 884 KB Output is correct
5 Correct 727 ms 1060 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 139 ms 600 KB Output is correct
9 Correct 266 ms 1168 KB Output is correct
10 Correct 707 ms 1212 KB Output is correct
11 Correct 790 ms 1484 KB Output is correct
12 Correct 761 ms 1284 KB Output is correct
13 Correct 793 ms 1040 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 56 ms 344 KB Output is correct
17 Correct 108 ms 344 KB Output is correct
18 Correct 143 ms 344 KB Output is correct
19 Correct 242 ms 680 KB Output is correct
20 Correct 320 ms 1104 KB Output is correct
21 Correct 810 ms 1496 KB Output is correct
22 Correct 737 ms 1392 KB Output is correct
23 Correct 782 ms 1156 KB Output is correct
24 Correct 735 ms 1408 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 5 ms 344 KB Output is correct
27 Correct 21 ms 344 KB Output is correct
28 Correct 24 ms 340 KB Output is correct
29 Correct 18 ms 344 KB Output is correct
30 Correct 179 ms 720 KB Output is correct
31 Correct 171 ms 344 KB Output is correct
32 Correct 189 ms 452 KB Output is correct
33 Correct 267 ms 548 KB Output is correct
34 Correct 264 ms 604 KB Output is correct
35 Correct 287 ms 728 KB Output is correct
36 Correct 719 ms 1380 KB Output is correct
37 Correct 793 ms 1376 KB Output is correct
38 Correct 761 ms 1120 KB Output is correct
39 Correct 747 ms 1096 KB Output is correct
40 Correct 831 ms 872 KB Output is correct
41 Correct 811 ms 1000 KB Output is correct
42 Correct 857 ms 1012 KB Output is correct
43 Correct 878 ms 972 KB Output is correct
44 Correct 871 ms 996 KB Output is correct
45 Correct 8 ms 344 KB Output is correct
46 Correct 7 ms 340 KB Output is correct
47 Correct 22 ms 344 KB Output is correct
48 Correct 32 ms 344 KB Output is correct
49 Correct 34 ms 344 KB Output is correct
50 Correct 203 ms 464 KB Output is correct
51 Correct 183 ms 344 KB Output is correct
52 Correct 204 ms 604 KB Output is correct
53 Correct 298 ms 592 KB Output is correct
54 Correct 294 ms 540 KB Output is correct
55 Correct 336 ms 688 KB Output is correct
56 Correct 752 ms 1056 KB Output is correct
57 Correct 764 ms 1016 KB Output is correct
58 Correct 774 ms 1104 KB Output is correct
59 Correct 730 ms 1108 KB Output is correct
60 Correct 867 ms 1148 KB Output is correct
61 Correct 826 ms 1248 KB Output is correct
62 Correct 870 ms 948 KB Output is correct
63 Correct 841 ms 876 KB Output is correct
64 Correct 792 ms 1212 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Partially correct 159 ms 344 KB Output is partially correct
4 Partially correct 393 ms 732 KB Output is partially correct
5 Partially correct 827 ms 1476 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Partially correct 159 ms 344 KB Output is partially correct
9 Partially correct 317 ms 632 KB Output is partially correct
10 Partially correct 814 ms 1232 KB Output is partially correct
11 Partially correct 878 ms 1292 KB Output is partially correct
12 Partially correct 799 ms 1068 KB Output is partially correct
13 Partially correct 735 ms 1368 KB Output is partially correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -