Submission #548385

#	Time	Username	Problem	Language	Result	Execution time	Memory
548385		ToroTN	Swapping Cities (APIO20_swap)	C++14	50 / 100	2053 ms	20276 KiB

swap

#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define X first
#define Y second
#define pb push_back

int n,m,dg[100005],u_i,v_i,w_i,x,y,type=-1,flag=-1;
int deter=2,d[1005][1005],st,md,ed,u1,u2,w,node,u;
int from[100005],p[100005],id[100005],chk,blk[100005];
int vis[100005];
vector<pair<int,int> > g[100005];
vector<pair<int,pair<int,int> > > v;
queue<pair<int,int> > q;
queue<int> qq;

int f(int a)
{
    if(p[a]==a)return a;
    return p[a]=f(p[a]);
}

void un(int b,int c)
{
    p[f(b)]=f(c);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        u_i=U[i]+1;
        v_i=V[i]+1;
        w_i=W[i];
        g[u_i].pb({v_i,w_i});
        g[v_i].pb({u_i,w_i});
        ++dg[u_i];
        ++dg[v_i];
        v.push_back({w_i,{u_i,v_i}});
        if(u_i!=1)flag=0;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        if(dg[i]>2)
        {
            type=0;
        }
    }
    if(type==-1)
    {
        deter=0;
        for(int i=1;i<=n;i++)if(dg[i]!=2)deter=-1;
    }
}

int getMinimumFuelCapacity(int X, int Y)
{

    x=X+1;
    y=Y+1;

    //subtask1
    if(type==-1)
    {
        if(deter==0)return v[v.size()-1].X;
        return -1;
    }

    //subtask2
    if(m==n-1&&flag==-1)
    {
        if(m<=2)return -1;
        if(x==1)
        {
            if(g[y][0].Y>v[2].X)return g[y][0].Y;
            return v[2].X;
        }
        if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
        return max(g[x][0].Y,g[y][0].Y);
    }

    //subtask3
    if(n<=1000&&m<=2000)
    {
        st=0;
        ed=v.size()-1;
        while(ed>=st)
        {
            md=(st+ed)/2;
            memset(d,0,sizeof d);
            d[x][y]=1;
            q.push({x,y});
            while(!q.empty())
            {
                u1=q.front().X;
                u2=q.front().Y;
                q.pop();
                for(int i=0;i<g[u1].size();i++)
                {
                    node=g[u1][i].X;
                    w=g[u1][i].Y;
                    if(v[md].X>=w&&node!=u2&&d[node][u2]==0)
                    {
                        d[node][u2]=1;
                        q.push({node,u2});
                    }
                }
                for(int i=0;i<g[u2].size();i++)
                {
                    node=g[u2][i].X;
                    w=g[u2][i].Y;
                    if(v[md].X>=w&&node!=u1&&d[u1][node]==0)
                    {
                        d[u1][node]=1;
                        q.push({u1,node});
                    }
                }
            }
            if(d[y][x]==1)
            {
                ed=md-1;
            }else
            {
                st=md+1;
            }
        }
        return v[st].X;
    }

    //subtask 4
    st=0;
    ed=v.size()-1;
    //printf("initial=%d %d\n",x,y);
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("group=%d %d %d\n",st,md,ed);
        for(int i=1;i<=n;i++)p[i]=i,id[i]=0;
        for(int i=0;i<=md;i++)
        {
            un(v[i].Y.X,v[i].Y.Y);
            ++id[v[i].Y.X];
            ++id[v[i].Y.Y];
        }
        if(f(x)!=f(y))
        {
            //printf("unequal parent\n");
            st=md+1;
        }else
        {
            chk=-1;
            for(int i=1;i<=n;i++)if(f(x)==f(i))if(id[i]>=3)chk=0;
            if(chk==0)
            {
                //printf("perfect with branch\n");
                ed=md-1;
            }else
            {
                for(int i=1;i<=n;i++)blk[i]=0,from[i]=-1;
                from[x]=0;
                qq.push(x);
                while(!qq.empty())
                {
                    u=qq.front();
                    qq.pop();
                    for(int i=0;i<g[u].size();i++)
                    {
                        node=g[u][i].X;
                        w=g[u][i].Y;
                        if(from[node]==-1&&w<=v[md].X)
                        {
                            from[node]=u;
                            qq.push(node);
                        }
                    }
                }
                u=y;
                while(1)
                {
                    u=from[u];
                    if(u==x)break;
                    blk[u]=1;
                }
                for(int i=1;i<=n;i++)vis[i]=0;
                vis[x]=1;
                qq.push(x);
                while(!qq.empty())
                {
                    u=qq.front();
                    qq.pop();
                    for(int i=0;i<g[u].size();i++)
                    {
                        node=g[u][i].X;
                        w=g[u][i].Y;
                        if(u==x&&node==y)continue;
                        if(blk[node]==0&&vis[node]==0&&w<=v[md].X)
                        {
                            vis[node]=1;
                            qq.push(node);
                        }
                    }
                }
                if(vis[y]==1)
                {
                    //printf("perfect\n");
                    ed=md-1;
                }else
                {
                    //printf("no cycle\n");
                    st=md+1;
                }
            }
        }
    }
    return v[st].X;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:82:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   82 |         if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
      |                       ^
swap.cpp:102:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                 for(int i=0;i<g[u1].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:112:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for(int i=0;i<g[u2].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:170:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |                     for(int i=0;i<g[u].size();i++)
      |                                 ~^~~~~~~~~~~~
swap.cpp:195:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |                     for(int i=0;i<g[u].size();i++)
      |                                 ~^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27