Submission #591549

#	Time	Username	Problem	Language	Result	Execution time	Memory
591549		yutabi	Roller Coaster Railroad (IOI16_railroad)	C++14	41 / 100	157 ms	13488 KiB

railroad

#include "railroad.h"


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


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;



ll DP[1<<16][16];
ll nw[1<<16][16];


ll maxi=1000000000000000007;


vector <int> srs;
bool srs2[1<<16];

vector <int> srs_nw;

vector <int> DSU;
 
 
int find_parent(int a)
{
    if(DSU[a]==a)
    {
        return a;
    }
 
    return DSU[a]=find_parent(DSU[a]);
}
 
bool make_union(int a, int b)
{
    a=find_parent(a);
    b=find_parent(b);
 
    if(a==b)
    {
        return 0;
    }
 
    DSU[b]=a;
 
    return 1;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
    int n = (int) s.size();

    if(n<16)
    {
    for(int i=0;i<1<<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            DP[i][j]=maxi;
        }
    }

    for(int i=0;i<n;i++)
    {
        DP[1<<i][i]=0;

        srs.pb(1<<i);

        srs2[1<<i]=1;
    }

    for(int l=0;l<n;l++)
    {
        for(int i=0;i<n;i++)
        {
            for(int _j=0;_j<srs.size();_j++)
            {
                int j=srs[_j];

                if(!((1<<i)&(j)))
                {
                    for(int k=0;k<n;k++)
                    {
                        DP[(1<<i)+j][i]=min(DP[(1<<i)+j][i],DP[j][k]+max(t[k]-s[i],0));
                    }

                    if(srs2[(1<<i)+j]==0)
                    {
                        srs_nw.pb((1<<i)+j);

                        srs2[(1<<i)+j]=1;
                    }
                }
            }
        }

        srs=srs_nw;

        srs_nw.clear();
    }

    ll ans=maxi;

    for(int i=0;i<n;i++)
    {
        ans=min(ans,DP[srs[0]][i]);
    }

    /*for(int i=0;i<1<<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%lld ",DP[i][j]);
        }

        printf("\n");
    }*/

    return ans;
    }

    else
    {
    vector <ii> nw_s;
    vector <ii> nw_t;
 
    for(int i=0;i<n;i++)
    {
        nw_s.pb(ii(s[i],i));
        nw_t.pb(ii(t[i],i));
    }
 
    vector <ii> nw;
 
    sort(nw_s.begin(),nw_s.end());
    sort(nw_t.begin(),nw_t.end());
 
    for(int i=0;i<n-1;i++)
    {
        nw.pb(ii(nw_t[i].second,nw_s[i+1].second));
    }
 
    nw.pb(ii(nw_t[n-1].second,nw_s[0].second));
 
 
    DSU=vector <int> (n);
 
    for(int i=0;i<n;i++)
    {
        DSU[i]=i;
    }
 
    ll ans=0;
 
    priority_queue <ii> pq;
 
    for(int i=0;i<n;i++)
    {
        make_union(nw[i].first,nw[i].second);
 
        if(i!=n-1)
        {
            ans+=max(t[nw[i].first]-s[nw[i].second],0);
 
            pq.push(ii(i,t[nw[i+1].first]-s[nw[i].second]));
        }
    }
 
    while(pq.size())
    {
        int ptr=pq.top().first;
        int num=pq.top().second;
 
        pq.pop();
 
        if(make_union(nw[ptr].first,nw[ptr+1].first))
        {
            ans+=max(0,num);
        }
    }
 
    return ans;
    }
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:83:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int _j=0;_j<srs.size();_j++)
      |                          ~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36