oj.uz

Submission #1019205

# Submission time Handle Problem Language Result Execution time Memory
1019205 2024-07-10T15:28:10 Z LIF Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 6868 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
int edge[5005][5005];
bool vis[5005];
int dep[5005];
int pre[5005];
bool in_queue[5005];
vector<int> longest_trip(int N, int D)
{
    for(int i=1;i<N;i++)
    {
        for(int j=0;j<i;j++)
        {
            vector<int> A;
            vector<int> B;
            A.push_back(i);
            B.push_back(j);
            if(are_connected(A,B) == true)
            {
                edge[j][i] = true;
                edge[i][j] = true;
            }
            else 
            {
                edge[j][i] = false;
                edge[i][j] = false;
            }

        }
    }
    vector<int> ans;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)vis[j] = false;
        for(int j=0;j<N;j++)pre[j] = -1;
        for(int j=0;j<N;j++)dep[j] = 0;
        for(int j=0;j<N;j++)in_queue[j] = false;
        vector<int> now;
        queue<int> q;
        q.push(i);
        dep[i] = 1;
        in_queue[i] = true;
        int cnt = 0;
        while(q.empty() == false)
        {
            cnt++;
            int fir = q.front();
            q.pop();
            if(vis[fir] == true)continue;
            vis[fir] = true;
            for(int j=0;j<N;j++)
            {
                if(edge[fir][j] == false)continue;
                if(dep[fir] + 1 > dep[j] && vis[j] == false)
                {
                    pre[j] = fir; 
                    dep[j] = dep[fir] + 1;
                    if(in_queue[j] == false)
                    {
                        q.push(j);
                        in_queue[j] = true;
                    }
                }
            }
        }
      //  cout<<"cnt: "<<cnt<<endl;
        vector<int> v;
        int maxn = -1;
        int maxid = 0;
       // for(int j=0;j<N;j++)cout<<dep[j]<<" "<<pre[j]<<" ";
        //cout<<endl;
        for(int j=0;j<N;j++)
        {
            if(dep[j] > maxn)
            {
                maxn = dep[j];
                maxid = j;
            }
        }
        
        while(maxid != -1)
        {
            v.push_back(maxid);
            maxid = pre[maxid];
        }
        if(v.size() > ans.size())ans = v;
    }
    
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 240 ms 6608 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 28 ms 2392 KB Output is correct
3 Correct 163 ms 2392 KB Output is correct
4 Correct 460 ms 4688 KB Output is correct
5 Correct 950 ms 6608 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 21 ms 2392 KB Output is correct
3 Correct 152 ms 2528 KB Output is correct
4 Correct 428 ms 4552 KB Output is correct
5 Correct 927 ms 6600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Incorrect 1 ms 2392 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 344 KB Output is correct
2 Correct 26 ms 2392 KB Output is correct
3 Correct 171 ms 2392 KB Output is correct
4 Correct 419 ms 4564 KB Output is correct
5 Correct 894 ms 6604 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 136 ms 2392 KB Output is correct
9 Correct 326 ms 2392 KB Output is correct
10 Correct 947 ms 6624 KB Output is correct
11 Correct 866 ms 6856 KB Output is correct
12 Correct 919 ms 6624 KB Output is correct
13 Correct 957 ms 6624 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 95 ms 2392 KB Output is correct
18 Correct 138 ms 2388 KB Output is correct
19 Correct 304 ms 2644 KB Output is correct
20 Correct 352 ms 2392 KB Output is correct
21 Execution timed out 1071 ms 6868 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 22 ms 2392 KB Output is correct
3 Partially correct 159 ms 2648 KB Output is partially correct
4 Partially correct 414 ms 4552 KB Output is partially correct
5 Partially correct 949 ms 6748 KB Output is partially correct
6 Correct 9 ms 344 KB Output is correct
7 Incorrect 1 ms 2392 KB Incorrect
8 Halted 0 ms 0 KB -