Submission #548365

#	Time	Username	Problem	Language	Result	Execution time	Memory
548365		ToroTN	Swapping Cities (APIO20_swap)	C++14	13 / 100	2083 ms	14040 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;
vector<pair<int,int> > g[100005];
vector<pair<int,pair<int,int> > > v;
queue<pair<int,int> > q;

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;
    if(type==-1)
    {
        if(deter==0)return v[v.size()-1].X;
        return -1;
    }
    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);
    }
    if(n<=1000&&m<=2000)
    {
        st=0;
        ed=1e9;
        //printf("%d %d\n",x,y);
        while(ed>=st)
        {
            md=(st+ed)/2;
            //printf("%d %d %d\n",st,md,ed);
            memset(d,0,sizeof d);
            d[x][y]=1;
            q.push({x,y});
            while(!q.empty())
            {
                u1=q.front().X;
                u2=q.front().Y;
                //printf("%d %d\n",u1,u2);
                q.pop();
                for(int i=0;i<g[u1].size();i++)
                {
                    node=g[u1][i].X;
                    w=g[u1][i].Y;
                    if(md>=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(md>=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 st;
    }
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:63:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   63 |         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:84: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]
   84 |                 for(int i=0;i<g[u1].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:94: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]
   94 |                 for(int i=0;i<g[u2].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
  115 | }
      | ^

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