Submission #436302

#	Time	Username	Problem	Language	Result	Execution time	Memory
436302		AmineWeslati	Fun Tour (APIO20_fun)	C++14	100 / 100	469 ms	27416 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

typedef pair<int,int>pi;
#define fi first
#define se second

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//----------------------

const int MX=1e5+10;
int N; 

int C;
void find_centroid(){
    vi sub(N);
    FOR(i,0,N) sub[i]=attractionsBehind(0,i);

    C=-1;
    FOR(i,0,N) if(sub[i]>=(N+1)/2){
        if(C==-1) C=i;
        else if(sub[i]<sub[C]) C=i; 
    }
}

vi distC(MX);
vector<vi>subb;
vector<set<pi,greater<pi>>>sub;
void divide(){
    FOR(i,0,N) distC[i]=hoursRequired(C,i);

    FOR(i,0,N) if(distC[i]==1) subb.pb(vi{i});

    assert(sz(subb)>=2);
    vi vis(N,0); 
    FOR(i,0,2){
        int c=subb[i][0];
        vi dist(N); 
        FOR(j,0,N) dist[j]=hoursRequired(c,j);

        FOR(j,0,N) if(j!=c && dist[j]==distC[j]-1) subb[i].pb(j); 
        for(int x: subb[i]) vis[x]=1;
    }
    vis[C]=1; if(sz(subb)>2) vis[subb[2][0]]=1;
    FOR(i,0,N) if(!vis[i]) subb[2].pb(i);


    FOR(i,0,sz(subb)){
        set<pi,greater<pi>>s; 
        for(int u: subb[i]) s.insert({distC[u],u});
        sub.pb(s);
    }
}

vi ans; 
void solve(){
    int nb=sz(subb);

    int u=C;
    FOR(j,0,nb){
       for(int i: subb[j]) if(distC[i]>distC[u]) u=i;
    }
    
    int merged=0;
    while(1){
        //merge if possible
        for(int i=0; i<nb && !merged; i++){
            int x=0;
            FOR(j,0,nb) if(i!=j) x+=sz(sub[j]);
            
            if(x<=sz(sub[i])){
                int j=0; if(i==0) j++;
                FOR(k,0,nb) if(k!=i && k!=j){
                    for(auto x: sub[k]) sub[j].insert(x);
                    sub[k].clear();
                }
                merged=1;


                //careful
                int prev=-1;
                if(sz(ans)) prev=ans.back();

                if(prev==-1) u=(*sub[i].begin()).se; 
                else{
                    if(distC[prev]>distC[u]) u=(*sub[i].begin()).se; 
                }
            }
        }


        //erase the current one & move to the next
        ans.pb(u);
        int idx; 
        FOR(i,0,nb) if(sub[i].count({distC[u],u})) 
            sub[i].erase({distC[u],u}),idx=i;
        
        int nxt=-1;
        FOR(i,0,nb) if(i!=idx && sz(sub[i])){
            int v=(*sub[i].begin()).se;
            if(nxt==-1) nxt=v; 
            else if(distC[v]>distC[nxt]) nxt=v; 
        }

        if(nxt==-1) break;
        u=nxt; 
    }
    ans.pb(C);
}

vi createFunTour(int N, int Q){
    if(N==2) return vi{0,1};

    ::N=N; 
    find_centroid();
    divide();

    solve();
    return ans; 

}

/*

7 400000
0 1 
0 5
0 6
1 2
1 4
2 3

*/

Compilation message (stderr)

fun.cpp: In function 'void solve()':
fun.cpp:107:31: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |         FOR(i,0,nb) if(i!=idx && sz(sub[i])){
      |                               ^

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