Submission #1019205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019205		LIF	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	1071 ms	6868 KiB

longesttrip

#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
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60