oj.uz

Submission #840068

# Submission time Handle Problem Language Result Execution time Memory
840068 2023-08-31T04:40:34 Z Fysty Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 1004 KB 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

#include "longesttrip.h"

bool has[300][300];
vector<int> ed[300];
bool vis[300];
int par[300];
int deg[300],cnt[300];
int n;

void dfs(int u)
{
    vis[u]=1;
    for(int v:ed[u]) if(!vis[v])
    {
        par[v]=u;
        cnt[u]++;
        dfs(v);
    }
}

void dfs2(int u,vector<int> &ret)
{
    vis[u]=1;
    ret.pb(u);
    for(int v:ed[u]) if(!vis[v]) dfs2(v,ret);
}



/*bool db[300][300];

bool are_connected(vector<int> a,vector<int> b)
{
    bool ret=0;
    for(int x:a) for(int y:b)
    {
        ret|=db[x][y];
    }
    return ret;
}*/

vector<int> longest_trip(int N,int D)
{
    n=N;
    rep(i,n)
    {
        rep(j,n)
        {
            has[i][j]=0;
        }
        ed[i].clear();
        vis[i]=0;
        par[i]=-1;
        deg[i]=cnt[i]=0;
    }
    vector<int> ret;
    if(D==3)
    {
        rep(i,n) ret.pb(i);
        return ret;
    }
    rep(i,n) rep(j,i)
    {
        bool res=are_connected({i},{j});
        if(res)
        {
            ed[i].pb(j);
            ed[j].pb(i);
            has[i][j]=has[j][i]=1;
            deg[i]++,deg[j]++;
        }
    }
    par[0]=-1;
    dfs(0);
    vector<int> a,b;
    rep(i,n)
    {
        if(vis[i]) a.pb(i);
        else b.pb(i);
    }
    if(!b.empty())
    {
        if(a.size()>b.size()) return a;
        else return b;
    }
    /*int r=-1;
    rep(i,n)
    {
        vis[i]=0;
        if(deg[i]==1) r=i;
    }
    if(r!=-1)
    {
        dfs2(r,ret);
        return ret;
    }*/
    rep(i,n) vis[i]=0;
    vector<int> tmp;
    int x;
    rep(i,n)
    {
        if(cnt[i]==0) tmp.pb(i);
        if(cnt[i]==2) x=i;
    }
    if(tmp.size()==1)
    {
        int cur=tmp[0];
        while(cur!=-1)
        {
            ret.pb(cur);
            cur=par[cur];
        }
        return ret;
    }
    vector<int> ret2;
    int cur=tmp[0];
    while(cur!=par[x])
    {
        ret.pb(cur);
        cur=par[cur];
    }
    cur=tmp[1];
    while(cur!=x)
    {
        ret2.pb(cur);
        cur=par[cur];
    }
    reverse(ret2.begin(),ret2.end());
    for(int v:ret2) ret.pb(v);
    if(x==0) return ret;

    vector<int> ret3;
    cur=par[x];
    while(cur!=-1)
    {
        ret3.pb(cur);
        cur=par[cur];
    }
    if(has[par[x]][tmp[0]])
    {
        reverse(ret.begin(),ret.end());
    }
    for(int v:ret3) ret.pb(v);
    return ret;
}

/*
void solve()
{
    int N,D;
    cin>>N>>D;
    rep(i,N)
    {
        rep(j,N) cin>>db[i][j];
    }
    auto ans=longest_trip(N,D);
    for(int x:ans) cout<<x<<" ";
}

signed main()
{
    MottoHayaku

    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}*/

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:173:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  173 |     cur=par[x];
      |         ~~~~~^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 233 ms 812 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 33 ms 208 KB Output is correct
3 Correct 167 ms 336 KB Output is correct
4 Correct 459 ms 368 KB Output is correct
5 Correct 944 ms 688 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 33 ms 208 KB Output is correct
8 Correct 131 ms 336 KB Output is correct
9 Correct 358 ms 372 KB Output is correct
10 Correct 882 ms 560 KB Output is correct
11 Execution timed out 1004 ms 604 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 43 ms 208 KB Output is correct
3 Correct 207 ms 340 KB Output is correct
4 Correct 485 ms 352 KB Output is correct
5 Execution timed out 1022 ms 656 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 208 KB Output is correct
2 Correct 25 ms 208 KB Output is correct
3 Partially correct 167 ms 340 KB Output is partially correct
4 Partially correct 530 ms 400 KB Output is partially correct
5 Partially correct 821 ms 1004 KB Output is partially correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 32 ms 208 KB Output is correct
8 Partially correct 212 ms 340 KB Output is partially correct
9 Partially correct 355 ms 384 KB Output is partially correct
10 Partially correct 840 ms 648 KB Output is partially correct
11 Partially correct 947 ms 640 KB Output is partially correct
12 Partially correct 805 ms 748 KB Output is partially correct
13 Partially correct 937 ms 820 KB Output is partially correct
14 Correct 13 ms 208 KB Output is correct
15 Correct 18 ms 208 KB Output is correct
16 Correct 64 ms 208 KB Output is correct
17 Partially correct 136 ms 336 KB Output is partially correct
18 Partially correct 183 ms 336 KB Output is partially correct
19 Partially correct 356 ms 368 KB Output is partially correct
20 Partially correct 410 ms 360 KB Output is partially correct
21 Correct 17 ms 208 KB Output is correct
22 Correct 13 ms 208 KB Output is correct
23 Correct 43 ms 208 KB Output is correct
24 Correct 31 ms 208 KB Output is correct
25 Correct 29 ms 208 KB Output is correct
26 Partially correct 219 ms 336 KB Output is partially correct
27 Partially correct 215 ms 344 KB Output is partially correct
28 Partially correct 206 ms 348 KB Output is partially correct
29 Partially correct 365 ms 352 KB Output is partially correct
30 Partially correct 345 ms 500 KB Output is partially correct
31 Partially correct 352 ms 364 KB Output is partially correct
32 Correct 15 ms 208 KB Output is correct
33 Correct 15 ms 208 KB Output is correct
34 Correct 21 ms 208 KB Output is correct
35 Correct 30 ms 208 KB Output is correct
36 Correct 41 ms 208 KB Output is correct
37 Partially correct 187 ms 464 KB Output is partially correct
38 Partially correct 264 ms 340 KB Output is partially correct
39 Partially correct 275 ms 336 KB Output is partially correct
40 Partially correct 410 ms 384 KB Output is partially correct
41 Partially correct 334 ms 388 KB Output is partially correct
42 Partially correct 256 ms 388 KB Output is partially correct
43 Partially correct 710 ms 556 KB Output is partially correct
44 Execution timed out 1035 ms 644 KB Time limit exceeded
45 Halted 0 ms 0 KB -