oj.uz

Submission #961068

# Submission time Handle Problem Language Result Execution time Memory
961068 2024-04-11T13:21:48 Z 12345678 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 807 ms 2120 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=305;

int qrs[nx][nx], vs[nx], m, cnt, u, v, l[nx], r[nx], st, ed, p;
vector<int> d[nx];

int query(int i, int j)
{
    if (i>j) swap(i, j);
    return qrs[i][j];
}

void dfs(int u)
{
    vs[u]=1;
    cnt++;
    for (auto v:d[u]) if (!vs[v]) dfs(v);
}

std::vector<int> longest_trip(int N, int D)
{
    for (int i=0; i<N; i++) d[i].clear(), vs[i]=0;
    for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) qrs[i][j]=are_connected(vector<int> {i}, vector<int> {j});
    for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (query(i, j)) d[i].push_back(j);
    cnt=0;
    dfs(0);
    vector<int> res;
    if (cnt!=N)
    {
        if (cnt>=N-cnt) m=1;
        for (int i=0; i<N; i++)
        {
            if (vs[i]&&m) res.push_back(i);
            if (!vs[i]&&!m) res.push_back(i);
        }
        return res;
    }
    st=ed=0;
    queue<pair<int, int>> q;
    q.push({0, 0});
    for (int i=0; i<N;i ++) vs[i]=0;
    vs[0]=1;
    while (!q.empty())
    {
        auto [u, p]=q.front();
        if (u!=0)
        {
            if (query(u, st)) r[u]=st, l[st]=u, st=u;
            else if (query(u, ed)) r[ed]=u, l[u]=ed, ed=u;
            else
            {
                r[ed]=st;
                l[st]=ed;
                st=u;
                ed=l[p];
                r[u]=p;
                l[p]=u;
            }
        }
        q.pop();
        for (auto v:d[u]) if (!vs[v]) vs[v]=1, q.push({v, u});
    }
    while (st!=ed) res.push_back(st), st=r[st];
    res.push_back(ed);
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 198 ms 1560 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 27 ms 600 KB Output is correct
3 Correct 116 ms 852 KB Output is correct
4 Correct 390 ms 1532 KB Output is correct
5 Correct 770 ms 1648 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 24 ms 344 KB Output is correct
3 Correct 131 ms 996 KB Output is correct
4 Correct 386 ms 996 KB Output is correct
5 Correct 743 ms 1944 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 142 ms 868 KB Output is correct
9 Correct 272 ms 1112 KB Output is correct
10 Correct 734 ms 1484 KB Output is correct
11 Correct 730 ms 1692 KB Output is correct
12 Correct 735 ms 1668 KB Output is correct
13 Correct 737 ms 1604 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 20 ms 344 KB Output is correct
3 Correct 131 ms 1368 KB Output is correct
4 Correct 353 ms 1268 KB Output is correct
5 Correct 741 ms 1672 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 124 ms 1232 KB Output is correct
9 Correct 304 ms 1492 KB Output is correct
10 Correct 768 ms 1628 KB Output is correct
11 Correct 694 ms 1948 KB Output is correct
12 Correct 761 ms 1744 KB Output is correct
13 Correct 734 ms 1472 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Incorrect 1 ms 600 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 496 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Partially correct 120 ms 600 KB Output is partially correct
4 Partially correct 389 ms 1256 KB Output is partially correct
5 Partially correct 752 ms 1772 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 135 ms 1228 KB Output is partially correct
9 Partially correct 280 ms 1264 KB Output is partially correct
10 Partially correct 807 ms 1872 KB Output is partially correct
11 Partially correct 760 ms 1432 KB Output is partially correct
12 Partially correct 774 ms 1940 KB Output is partially correct
13 Partially correct 773 ms 2120 KB Output is partially correct
14 Incorrect 1 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -