oj.uz

Submission #840759

# Submission time Handle Problem Language Result Execution time Memory
840759 2023-08-31T16:46:41 Z firewater Longest Trip (IOI23_longesttrip) C++17
15 / 100
 24 ms 2764 KB 
#include<bits/stdc++.h>
#include "longesttrip.h"
#define MX 100100
using namespace std;

int n,now,x,y,z,xx,yy,gg,zz,to[MX];
vector<int>A,B,ans,ans1,ans2,a[MX];
// queue<int>d;
// bool are_connected(std::vector<int> A, std::vector<int> B)
bool check(int x,int y)
{
    A.clear();B.clear();
    A.push_back(x);
    B.push_back(y);
    return are_connected(A,B);
}
bool checkk(int x,vector<int> G)
{
    A.clear();
    A.push_back(x);
    return are_connected(A,G);
}
bool checkkk(int x,vector<int> G)
{
    A.clear();
    for(int i=0;i<=x;++i)
        A.push_back(ans1[i]);
    return are_connected(A,G);
}
bool checkkkk(int x,int y)
{
    A.clear();
    A.push_back(x);
    B.clear();
    for(int i=0;i<=y;++i)
        B.push_back(ans2[i]);
    return are_connected(A,B);
}
void dfs(int x,int fa)
{
    ans1.push_back(x);
    for(int i=0;i<a[x].size();++i)
        if(a[x][i]!=fa)
            dfs(a[x][i],x);
    return;
}
void dfss(int x,int fa)
{
    ans2.push_back(x);
    for(int i=0;i<a[x].size();++i)
        if(a[x][i]!=fa)
            dfss(a[x][i],x);
    return;
}
mt19937 gy(2018729);
int rd(int l,int r)
{
    return gy()%(r-l+1)+l;
}
std::vector<int> longest_trip(int N, int D)
{
    n=N;
    for(int i=0;i<n;++i)
        a[i].clear();
    
    x=0;
    to[x]=x;
    y=1;
    to[y]=y;
    gg=0;
    for(int i=2;i<n;++i){
        z=i;
        to[z]=z;
        if(check(x,z)){
            a[x].push_back(z);
            a[z].push_back(x);
            xx=to[x];
            zz=to[z];
            to[xx]=zz;
            to[zz]=xx;
            x=xx;
            gg=0;
        }
        else if(!gg&&check(x,y)){
            a[x].push_back(y);
            a[y].push_back(x);
            xx=to[x];
            yy=to[y];
            to[xx]=yy;
            to[yy]=xx;
            x=xx;y=z;
            gg=0;
        }
        else {
            a[y].push_back(z);
            a[z].push_back(y);
            yy=to[y];
            zz=to[z];
            to[yy]=zz;
            to[zz]=yy;
            y=yy;
            gg=1;
        }
    }
    ans1.clear();
    ans2.clear();
    ans.clear();
    dfs(x,x);
    dfss(y,y);
    if(!are_connected(ans1,ans2)){
        if(ans1.size()>ans2.size())return ans1;
        else return ans2;
    }
    xx=to[x];
    yy=to[y];
    A.clear();
    B.clear();
    A.push_back(x);
    if(x!=xx)A.push_back(xx);
    B.push_back(y);
    if(y!=yy)B.push_back(yy);
    if(are_connected(A,B)){
        if(check(x,y)){
            for(int i=ans1.size()-1;i>=0;--i)
                ans.push_back(ans1[i]);
            for(int i=0;i<ans2.size();++i)
                ans.push_back(ans2[i]);
        }
        else if(check(x,yy)){
            for(int i=ans1.size()-1;i>=0;--i)
                ans.push_back(ans1[i]);
            for(int i=ans2.size()-1;i>=0;--i)
                ans.push_back(ans2[i]);
        }
        else if(check(xx,y)){
            for(int i=0;i<ans1.size();++i)
                ans.push_back(ans1[i]);
            for(int i=0;i<ans2.size();++i)
                ans.push_back(ans2[i]);
        }
        else if(check(xx,yy)){
            for(int i=0;i<ans1.size();++i)
                ans.push_back(ans1[i]);
            for(int i=ans2.size()-1;i>=0;--i)
                ans.push_back(ans2[i]);
        }
    }
    else{
        int l=0,r=ans1.size()-1;
        while(l<r){
            int mid=l+r>>1;
            if(checkkk(mid,ans2))r=mid;
            else l=mid+1;
        }
        int sav=l;
        l=0;r=ans2.size()-1;
        while(l<r){
            int mid=l+r>>1;
            if(checkkkk(ans1[sav],mid))r=mid;
            else l=mid+1;
        }
        int i=sav,j=l;
               for(int k=i+1;k<ans1.size();++k)
                    ans.push_back(ans1[k]);
               for(int k=0;k<=i;++k)
                    ans.push_back(ans1[k]);
               for(int k=j;k<ans2.size();++k)
                    ans.push_back(ans2[k]);
               for(int k=0;k<j;++k)
                    ans.push_back(ans2[k]);
            return ans;
    }
    return ans;
}

Compilation message

longesttrip.cpp: In function 'void dfs(int, int)':
longesttrip.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<a[x].size();++i)
      |                 ~^~~~~~~~~~~~
longesttrip.cpp: In function 'void dfss(int, int)':
longesttrip.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<a[x].size();++i)
      |                 ~^~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:126:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for(int i=0;i<ans2.size();++i)
      |                         ~^~~~~~~~~~~~
longesttrip.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for(int i=0;i<ans1.size();++i)
      |                         ~^~~~~~~~~~~~
longesttrip.cpp:138:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             for(int i=0;i<ans2.size();++i)
      |                         ~^~~~~~~~~~~~
longesttrip.cpp:142:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             for(int i=0;i<ans1.size();++i)
      |                         ~^~~~~~~~~~~~
longesttrip.cpp:151:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |             int mid=l+r>>1;
      |                     ~^~
longesttrip.cpp:158:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |             int mid=l+r>>1;
      |                     ~^~
longesttrip.cpp:163:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                for(int k=i+1;k<ans1.size();++k)
      |                              ~^~~~~~~~~~~~
longesttrip.cpp:167:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |                for(int k=j;k<ans2.size();++k)
      |                            ~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 3 ms 2640 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2640 KB Output is correct
2 Correct 11 ms 2640 KB Output is correct
3 Correct 11 ms 2640 KB Output is correct
4 Correct 9 ms 2640 KB Output is correct
5 Correct 9 ms 2640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2640 KB Output is correct
2 Correct 8 ms 2640 KB Output is correct
3 Correct 11 ms 2640 KB Output is correct
4 Correct 10 ms 2640 KB Output is correct
5 Correct 6 ms 2640 KB Output is correct
6 Correct 14 ms 2640 KB Output is correct
7 Correct 10 ms 2640 KB Output is correct
8 Correct 13 ms 2640 KB Output is correct
9 Correct 12 ms 2668 KB Output is correct
10 Correct 7 ms 2640 KB Output is correct
11 Correct 8 ms 2640 KB Output is correct
12 Correct 10 ms 2640 KB Output is correct
13 Correct 6 ms 2640 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2640 KB Output is correct
2 Correct 7 ms 2640 KB Output is correct
3 Correct 11 ms 2640 KB Output is correct
4 Correct 7 ms 2640 KB Output is correct
5 Correct 9 ms 2640 KB Output is correct
6 Correct 13 ms 2640 KB Output is correct
7 Correct 12 ms 2640 KB Output is correct
8 Correct 14 ms 2640 KB Output is correct
9 Correct 7 ms 2640 KB Output is correct
10 Correct 8 ms 2640 KB Output is correct
11 Correct 11 ms 2640 KB Output is correct
12 Correct 11 ms 2640 KB Output is correct
13 Correct 14 ms 2640 KB Output is correct
14 Correct 11 ms 2640 KB Output is correct
15 Correct 11 ms 2640 KB Output is correct
16 Incorrect 3 ms 2640 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2640 KB Output is correct
2 Correct 10 ms 2640 KB Output is correct
3 Correct 9 ms 2764 KB Output is correct
4 Correct 11 ms 2588 KB Output is correct
5 Correct 8 ms 2664 KB Output is correct
6 Correct 24 ms 2640 KB Output is correct
7 Correct 12 ms 2640 KB Output is correct
8 Correct 9 ms 2640 KB Output is correct
9 Correct 7 ms 2640 KB Output is correct
10 Correct 7 ms 2668 KB Output is correct
11 Correct 10 ms 2640 KB Output is correct
12 Correct 9 ms 2640 KB Output is correct
13 Correct 8 ms 2640 KB Output is correct
14 Correct 9 ms 2640 KB Output is correct
15 Correct 14 ms 2640 KB Output is correct
16 Incorrect 2 ms 2640 KB Incorrect
17 Halted 0 ms 0 KB -