oj.uz

Submission #1019204

# Submission time Handle Problem Language Result Execution time Memory
1019204 2024-07-10T15:27:22 Z LIF Longest Trip (IOI23_longesttrip) C++17
5 / 100
 902 ms 6860 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<1;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 1 ms 344 KB Output is correct
2 Incorrect 212 ms 6608 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 21 ms 2392 KB Output is correct
3 Correct 143 ms 2520 KB Output is correct
4 Correct 401 ms 4432 KB Output is correct
5 Correct 902 ms 6604 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 36 ms 2392 KB Output is correct
3 Correct 148 ms 2520 KB Output is correct
4 Correct 401 ms 4428 KB Output is correct
5 Correct 854 ms 6608 KB Output is correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 2392 KB Output is correct
3 Correct 168 ms 2388 KB Output is correct
4 Correct 439 ms 4560 KB Output is correct
5 Correct 829 ms 6608 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 172 ms 2648 KB Output is correct
9 Correct 324 ms 2392 KB Output is correct
10 Correct 841 ms 6736 KB Output is correct
11 Correct 863 ms 6860 KB Output is correct
12 Correct 827 ms 6604 KB Output is correct
13 Correct 856 ms 6612 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Incorrect 1 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 22 ms 2392 KB Output is correct
3 Partially correct 137 ms 2392 KB Output is partially correct
4 Partially correct 408 ms 4812 KB Output is partially correct
5 Partially correct 843 ms 6740 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -