oj.uz

Submission #842066

# Submission time Handle Problem Language Result Execution time Memory
842066 2023-09-02T11:03:58 Z Tenis0206 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 741 ms 1652 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"

using namespace std;

const int nmax = 256;

int n;

std::vector<int> G[nmax + 5];

int d[nmax + 5];

bool sel[nmax + 5];
int t[nmax + 5];

int split, l1, l2;

int find_next_go(int nod)
{
    for(auto it : G[nod])
    {
        if(!sel[it])
        {
            return it;
        }
    }
    return -1;
}

void dfs(int nod)
{
    sel[nod] = true;
    int son = find_next_go(nod);
    int nr_sons = 0;
    while(son!=-1)
    {
        t[son] = nod;
        dfs(son);
        son = find_next_go(nod);
        ++nr_sons;
    }
    if(nr_sons==2)
    {
        split = nod;
    }
    if(!nr_sons)
    {
        if(l1==-1)
        {
            l1 = nod;
        }
        else
        {
            l2 = nod;
        }
    }
}

std::vector<int> longest_trip(int N, int D)
{
    n = N;
    for(int i=0;i<n;i++)
    {
        G[i].clear();
        sel[i] = false;
        t[i] = -1;
    }
    split = -1, l1 = -1, l2 = -1;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(are_connected({i}, {j}))
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    dfs(0);
    vector<int> r;
    if(l2==-1)
    {
        int nod = l1;
        r.push_back(l1);
        while(nod)
        {
            nod = t[nod];
            r.push_back(nod);
        }
        return r;
    }
    vector<int> a,b;
    bool ok = false;
    for(auto it : G[l1])
    {
        if(it==0)
        {
            ok = true;
        }
    }
    if(!ok)
    {
        swap(l1,l2);
    }
    int nod = l1;
    while(nod!=split)
    {
        a.push_back(nod);
        nod = t[nod];
    }
    reverse(a.begin(),a.end());
    nod = l2;
    b.push_back(nod);
    while(nod)
    {
        nod = t[nod];
        b.push_back(nod);
    }
    reverse(b.begin(),b.end());
    for(auto it : a)
    {
        r.push_back(it);
    }
    for(auto it : b)
    {
        r.push_back(it);
    }
    return r;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 129 ms 604 KB Output is correct
4 Correct 351 ms 856 KB Output is correct
5 Correct 707 ms 1248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 124 ms 692 KB Output is correct
4 Correct 357 ms 856 KB Output is correct
5 Correct 709 ms 1248 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 23 ms 500 KB Output is correct
8 Correct 125 ms 856 KB Output is correct
9 Correct 251 ms 964 KB Output is correct
10 Correct 708 ms 1480 KB Output is correct
11 Correct 698 ms 1252 KB Output is correct
12 Correct 695 ms 1352 KB Output is correct
13 Correct 692 ms 1384 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 127 ms 864 KB Output is correct
4 Correct 356 ms 1112 KB Output is correct
5 Correct 712 ms 1220 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Correct 119 ms 856 KB Output is correct
9 Correct 297 ms 960 KB Output is correct
10 Correct 727 ms 1396 KB Output is correct
11 Correct 657 ms 1116 KB Output is correct
12 Correct 734 ms 1396 KB Output is correct
13 Correct 639 ms 1312 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 24 ms 340 KB Output is correct
3 Partially correct 124 ms 1112 KB Output is partially correct
4 Partially correct 320 ms 968 KB Output is partially correct
5 Partially correct 687 ms 1652 KB Output is partially correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Partially correct 130 ms 1112 KB Output is partially correct
9 Partially correct 266 ms 980 KB Output is partially correct
10 Partially correct 730 ms 1140 KB Output is partially correct
11 Partially correct 671 ms 1116 KB Output is partially correct
12 Partially correct 716 ms 1636 KB Output is partially correct
13 Partially correct 741 ms 1588 KB Output is partially correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -