oj.uz

Submission #842072

# Submission time Handle Problem Language Result Execution time Memory
842072 2023-09-02T11:11:27 Z Tenis0206 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 758 ms 2012 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> solve_component(int root)
{
    dfs(root);
    vector<int> r;
    if(l2==-1)
    {
        int nod = l1;
        r.push_back(l1);
        while(nod!=root)
        {
            nod = t[nod];
            r.push_back(nod);
        }
        return r;
    }
    vector<int> a,b;
    bool ok = false;
    for(auto it : G[l1])
    {
        if(it==root)
        {
            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!=root)
    {
        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;
}

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);
            }
        }
    }
    vector<int> r;
    vector<int> aux = solve_component(0);
    if(aux.size() > r.size())
    {
        r = aux;
    }
    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 156 ms 1656 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 25 ms 344 KB Output is correct
3 Correct 124 ms 1116 KB Output is correct
4 Correct 325 ms 1192 KB Output is correct
5 Correct 647 ms 2012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 124 ms 704 KB Output is correct
4 Correct 330 ms 1200 KB Output is correct
5 Correct 742 ms 1204 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Correct 119 ms 600 KB Output is correct
9 Correct 262 ms 956 KB Output is correct
10 Correct 660 ms 1312 KB Output is correct
11 Correct 662 ms 1312 KB Output is correct
12 Correct 674 ms 980 KB Output is correct
13 Correct 683 ms 1600 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 125 ms 704 KB Output is correct
4 Correct 334 ms 1128 KB Output is correct
5 Correct 703 ms 1304 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 130 ms 856 KB Output is correct
9 Correct 256 ms 1116 KB Output is correct
10 Correct 665 ms 1504 KB Output is correct
11 Correct 678 ms 1644 KB Output is correct
12 Correct 694 ms 1116 KB Output is correct
13 Correct 705 ms 1232 KB Output is correct
14 Correct 5 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 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Partially correct 136 ms 600 KB Output is partially correct
4 Partially correct 347 ms 868 KB Output is partially correct
5 Partially correct 758 ms 1252 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 126 ms 600 KB Output is partially correct
9 Partially correct 297 ms 1380 KB Output is partially correct
10 Partially correct 692 ms 1540 KB Output is partially correct
11 Partially correct 717 ms 1388 KB Output is partially correct
12 Partially correct 737 ms 1376 KB Output is partially correct
13 Partially correct 681 ms 1396 KB Output is partially correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -