oj.uz

Submission #1071885

# Submission time Handle Problem Language Result Execution time Memory
1071885 2024-08-23T12:07:15 Z mindiyak Longest Trip (IOI23_longesttrip) C++17
30 / 100
 919 ms 1504 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(i,0,N){
        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 180 ms 1124 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 163 ms 448 KB Output is correct
4 Correct 433 ms 604 KB Output is correct
5 Correct 888 ms 1436 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 150 ms 344 KB Output is correct
4 Correct 419 ms 900 KB Output is correct
5 Correct 847 ms 1292 KB Output is correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 34 ms 344 KB Output is correct
3 Correct 166 ms 344 KB Output is correct
4 Correct 425 ms 720 KB Output is correct
5 Correct 852 ms 1140 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 35 ms 340 KB Output is correct
8 Correct 157 ms 592 KB Output is correct
9 Correct 349 ms 724 KB Output is correct
10 Correct 919 ms 1204 KB Output is correct
11 Correct 897 ms 1132 KB Output is correct
12 Correct 851 ms 1220 KB Output is correct
13 Correct 850 ms 1324 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 36 ms 344 KB Output is correct
17 Correct 87 ms 344 KB Output is correct
18 Correct 172 ms 464 KB Output is correct
19 Correct 329 ms 676 KB Output is correct
20 Correct 341 ms 792 KB Output is correct
21 Correct 810 ms 1504 KB Output is correct
22 Correct 881 ms 1088 KB Output is correct
23 Correct 812 ms 1088 KB Output is correct
24 Correct 779 ms 1436 KB Output is correct
25 Correct 8 ms 344 KB Output is correct
26 Correct 10 ms 344 KB Output is correct
27 Correct 21 ms 344 KB Output is correct
28 Correct 27 ms 344 KB Output is correct
29 Correct 30 ms 344 KB Output is correct
30 Correct 195 ms 344 KB Output is correct
31 Correct 197 ms 684 KB Output is correct
32 Correct 192 ms 456 KB Output is correct
33 Correct 336 ms 788 KB Output is correct
34 Correct 328 ms 780 KB Output is correct
35 Correct 329 ms 788 KB Output is correct
36 Correct 812 ms 1376 KB Output is correct
37 Correct 892 ms 1100 KB Output is correct
38 Correct 864 ms 908 KB Output is correct
39 Correct 791 ms 872 KB Output is correct
40 Correct 803 ms 864 KB Output is correct
41 Correct 807 ms 1012 KB Output is correct
42 Correct 810 ms 964 KB Output is correct
43 Correct 812 ms 1136 KB Output is correct
44 Correct 840 ms 864 KB Output is correct
45 Correct 8 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 32 ms 344 KB Output is correct
48 Correct 31 ms 344 KB Output is correct
49 Correct 21 ms 344 KB Output is correct
50 Correct 180 ms 480 KB Output is correct
51 Correct 178 ms 704 KB Output is correct
52 Correct 185 ms 448 KB Output is correct
53 Correct 312 ms 848 KB Output is correct
54 Correct 280 ms 592 KB Output is correct
55 Correct 312 ms 548 KB Output is correct
56 Correct 774 ms 1288 KB Output is correct
57 Correct 839 ms 1288 KB Output is correct
58 Correct 763 ms 988 KB Output is correct
59 Correct 854 ms 1392 KB Output is correct
60 Correct 816 ms 1100 KB Output is correct
61 Correct 805 ms 1200 KB Output is correct
62 Correct 885 ms 776 KB Output is correct
63 Correct 854 ms 1028 KB Output is correct
64 Correct 847 ms 1112 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 21 ms 348 KB Output is correct
3 Partially correct 178 ms 344 KB Output is partially correct
4 Partially correct 425 ms 696 KB Output is partially correct
5 Partially correct 896 ms 1300 KB Output is partially correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -