Submission #394194

#	Time	Username	Problem	Language	Result	Execution time	Memory
394194		BJoozz	Fun Tour (APIO20_fun)	C++14	100 / 100	411 ms	20580 KiB

fun

#include<bits/stdc++.h>
using namespace std;
#include "fun.h"
#define X first
#define Y second
#define pb push_back
#define getdis hoursRequired
#define getsz attractionsBehind
const int MAX=100005,mod=1e9+7,M=2000,inf=1e9;
void maxx(int &a,int b){if(b>a) a=b;}
using ii = pair < int ,int > ;
void minn(int &a,int b){if(b<a) a=b;}
void maxp(ii &a,ii b){if(b>a) a=b;}
void minp(ii &a,ii b){if(b<a) a=b;}
bool cp(ii &a,ii b){if(b>a) {a=b;return 1;}else return 0;}
void PL(int &a,int b){a+=b;if(a>=mod) a-=mod;}


///+++++++++++++++++++++++++++++
int a[MAX],sz[4],h[MAX];
bool vs[MAX];
int D[4];
short bel[MAX];
int L[4][MAX];
int getdeep(int v){
    ii u = ii (0,0);
    int r;
    for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
        if( cp(u,ii(h[L[i][sz[i]]],sz[i])) ) r=i;
    return r;
}
bool cmp(int u,int v){
return h[u]<h[v];}
std::vector<int> createFunTour(int n,int Q){
    vector < int > vec;
    a[0]=n;
    if(n==2){
        vec.pb(0);vec.pb(1);return vec;
    }
    int r=0;
    for(int i=1;i<n;i++){
        a[i]=getsz(0,i);
        if(a[i]>n/2 && a[i]<a[r]) {
            r=i;
        }
    }
    int cn=0;
    for(int i=0;i<n;i++)if(r!=i){
        h[i]=getdis(r,i);
        if(h[i]==1) D[++cn]=i;
    }
    vs[r]=1;
    for(int i=1,u;i<=cn;i++){
        u=D[i];
        bel[u]=i;
        L[i][1]=u;
        vs[u]=1;
        sz[i]=getsz(r,u);
        ///co the toi uu
    }
    int top[4]={1,1,1,1};
    for(int i=0;i<n;i++) if(!vs[i]){
        if(getdis(D[1],i)==h[i]-1){
            bel[i]=1;
        }
        else{
            if(getdis(D[2],i)==h[i]-1)
            bel[i]=2;
            else bel[i]=3;
        }
        L[bel[i]][++top[bel[i]]]=i;
        //cout<<i<<' '<<bel[i]<<'\n';
    }

    for(int i=1;i<=cn;i++){
        sort(L[i]+1,L[i]+1+sz[i],cmp);
    }
    int las=0;
    int allsz=n;
    bool okk=1;
    for(int i=1;i<n && okk;i++){
        int z=getdeep(las);
        int v=L[z][sz[z]];
        vec.pb(v);
        sz[z]--;
        allsz--;
        las=z;

        for(int i=1;i<=cn;i++)
            if(sz[i]>=allsz/2){
                okk=0;break;
            }
    }
    if(!okk && allsz>1){
        int sp;
        for(int i=1;i<=cn;i++)
            if(sz[i]>=allsz/2){
                sp=i;break;
            }
            int z=getdeep(0);
            if(z!=las && z!=sp){
                int v=L[z][sz[z]];
                vec.pb(v);
                sz[z]--;
                allsz--;
                las=z;
            }
        bool turn=(las!=sp);
        //for ( int u:vec) cout<<u<<' ';cout<<'\n';
        //cout<<las<<' '<<sp<<'\n';
        //cout<<allsz;return vec;
        //cout<<sz[sp]<<' '<<allsz<<'\n';
        while(allsz>1){
            if(turn){
                int z=sp;
                if(sz[z]==0) {turn^=1;continue;}
                int v=L[z][sz[z]];
                vec.pb(v);
                sz[z]--;
                allsz--;
                las=z;
            }
            else{
                int z=getdeep(sp);
                if(sz[z]==0) {turn^=1;continue;}
                int v=L[z][sz[z]];
                vec.pb(v);
                sz[z]--;
                allsz--;
                las=z;
            }
            turn^=1;
        }
    }
    vec.pb(r);
    //cout<<allsz<<'\n';
    return vec;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:96:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |         for(int i=1;i<=cn;i++)
      |         ^~~
fun.cpp:100:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |             int z=getdeep(0);
      |             ^~~
fun.cpp: In function 'int getdeep(int)':
fun.cpp:30:12: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     return r;
      |            ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:104:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |                 sz[z]--;
      |                 ~~~~~^~
fun.cpp:28:27: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |     for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
      |                           ^~
fun.cpp:27:9: note: 'r' was declared here
   27 |     int r;
      |         ^

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34