oj.uz

Submission #1007024

# Submission time Handle Problem Language Result Execution time Memory
1007024 2024-06-24T10:57:51 Z edogawa_something Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 106228 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first 
#define S second 
#define all(v) v.begin(),v.end()
const int M=1010;
const ll inf=1e18;
struct dsu{
    ll sz[M],pa[M];
    void init(ll x){
        for(int i=0;i<=x;i++)
        pa[i]=i,sz[i]=1;
    }
    ll get(ll x){
        if(x==pa[x])
        return x;
        return pa[x]=get(pa[x]);
    }
    void unite(ll x,ll y){
        x=get(x),y=get(y);
        if(x==y)
        return;
        if(sz[x]<sz[y])
        swap(x,y);
        pa[y]=x;
        sz[x]+=sz[y];
    }
    bool same(ll x,ll y){
        return (get(x)==get(y));
    }
}d;
ll n;
bool edge[M][M],vis[M];
bool used[M];
vector<int>ans,adj[M];
void dfs(ll x){
    if(vis[x])
    return;
    vis[x]=1;
    for(auto it:adj[x]){
        dfs(it);
    }
}
bool cchk(ll i,ll j){
    if(!edge[i][j])
    return 0;
    bool c1[260];
    memset(c1,0,sizeof c1);
    for(auto it:adj[i]){
        if(it!=j)
        c1[it]=1;
    }
    for(auto it:adj[j]){
        if(it!=i&&!c1[it])
        return 1;
    }
    return 0;
}
deque<int>dp[260][260];
vector<int> solve(ll x,ll y){
    vii v;
    v.pb(x),v.pb(y);
    for(int i=0;i<n;i++){
        if(i==x||i==y)
        continue;
        v.pb(i);
    }
    for(int i=2;i<v.size();i++){
        bool c=0;
        for(int j=i-2;j>=0;j--){
            if(edge[v[i]][v[i-1]]&&dp[j][i-1].size()>0){
            dp[j][i]=dp[j][i-1];
            dp[j][i].pb(v[i]);
            dp[i][j]=dp[i-1][j];
            dp[i][j].push_front(v[i]);
            }
            if(edge[v[i]][v[j]]&&dp[j][i-1].size()>0&&!c){
                dp[i-1][i]=dp[i-1][j];
                dp[i-1][i].pb(v[i]);
                dp[i][i-1]=dp[j][i-1];
                dp[i][i-1].push_front(v[i]);
                c=1;
            }
        }
    }
    vector<int>res;
    for(int i=0;i<n-1;i++){
        if(dp[i][n-1].size()>0){
            for(auto it:dp[i][n-1])
            res.pb(it);
            return res;
        }
    }
    return res;
}
std::vector<int> longest_trip(int N, int D)
{
    memset(vis,0,sizeof vis);
    n=N;
    for(int i=0;i<n;i++)
    adj[i].clear();
    for(int i=0;i<n;i++){
        used[i]=0;
        for(int j=0;j<n;j++)
        dp[i][j].clear();
    }
    d.init(n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            edge[i][j]=edge[j][i]=are_connected({i},{j});
            if(edge[i][j])
            adj[i].pb(j),adj[j].pb(i);
        }
    }
    dfs(0);
    bool chk=0;
    for(int i=0;i<n;i++){
        if(!vis[i])
        chk=1;
    }
    if(chk){
        vector<int>v1,v2;
        v1.pb(0);
        for(int i=1;i<n;i++){
            if(edge[i][0])
            v1.pb(i);
            else
            v2.pb(i);
        }
        if(v1.size()<v2.size())
        swap(v1,v2);
        return v1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)
            continue;
            if(cchk(i,j)){
                dp[0][1].pb(i),dp[0][1].pb(j);
                dp[1][0].pb(j),dp[1][0].pb(i);
                return solve(i,j);
            }
        }
    }
    ans.clear();
    if(ans.empty()){
        for(int i=0;i<n;i++)
        ans.pb(i);
    }
    return ans;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> solve(ll, ll)':
longesttrip.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=2;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 46936 KB Output is correct
2 Correct 212 ms 49396 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 46936 KB Output is correct
2 Correct 45 ms 46892 KB Output is correct
3 Correct 168 ms 46936 KB Output is correct
4 Correct 441 ms 47252 KB Output is correct
5 Correct 856 ms 47376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 46936 KB Output is correct
2 Correct 44 ms 46936 KB Output is correct
3 Correct 147 ms 46936 KB Output is correct
4 Correct 441 ms 47016 KB Output is correct
5 Correct 843 ms 47484 KB Output is correct
6 Correct 25 ms 46936 KB Output is correct
7 Correct 47 ms 46912 KB Output is correct
8 Correct 174 ms 47652 KB Output is correct
9 Correct 340 ms 52236 KB Output is correct
10 Correct 979 ms 106220 KB Output is correct
11 Correct 945 ms 96040 KB Output is correct
12 Correct 930 ms 78348 KB Output is correct
13 Correct 882 ms 94536 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 46936 KB Output is correct
2 Correct 46 ms 46936 KB Output is correct
3 Correct 165 ms 46936 KB Output is correct
4 Correct 439 ms 46936 KB Output is correct
5 Correct 935 ms 47164 KB Output is correct
6 Correct 26 ms 46936 KB Output is correct
7 Correct 53 ms 46924 KB Output is correct
8 Correct 187 ms 47652 KB Output is correct
9 Correct 350 ms 52560 KB Output is correct
10 Execution timed out 1056 ms 106228 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 46932 KB Output is correct
2 Correct 41 ms 46936 KB Output is correct
3 Partially correct 152 ms 47192 KB Output is partially correct
4 Partially correct 487 ms 47012 KB Output is partially correct
5 Partially correct 922 ms 47500 KB Output is partially correct
6 Correct 37 ms 46980 KB Output is correct
7 Correct 43 ms 46936 KB Output is correct
8 Partially correct 156 ms 47696 KB Output is partially correct
9 Partially correct 361 ms 52236 KB Output is partially correct
10 Partially correct 922 ms 106224 KB Output is partially correct
11 Partially correct 941 ms 96180 KB Output is partially correct
12 Partially correct 877 ms 78344 KB Output is partially correct
13 Partially correct 914 ms 94540 KB Output is partially correct
14 Correct 27 ms 46836 KB Output is correct
15 Incorrect 24 ms 46936 KB Incorrect
16 Halted 0 ms 0 KB -