Submission #347941

#	Time	Username	Problem	Language	Result	Execution time	Memory
347941		MvC	Swapping Cities (APIO20_swap)	C++14	100 / 100	393 ms	44200 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,m,d[nmax],sz[nmax],p[nmax],gd[nmax],gud[nmax],x,y,rs,vl,mx[nmax],i,j;
vector<pair<int,pair<int,int> > >g;
vector<pair<int,int> >v[nmax];
vector<int>vc[nmax];
int fnd(int x)
{
    if(p[x]==x)return x;
    return p[x]=fnd(p[x]);
}
void uni(int x,int y,int z)
{
    d[x]++,d[y]++;
    int px=fnd(x),py=fnd(y),i;
    if(px==py)
    {
        if(!gd[px])
        {
            gd[px]=1;
            for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
        }
        return;
    }
    if(sz[px]<sz[py])
    {
        swap(px,py);
        swap(x,y);
    }
    p[py]=px;
    sz[px]+=sz[py];
    mx[px]=max(max(mx[px],mx[py]),max(d[x],d[y]));
    if(gd[px] && !gd[py])
    {
        for(i=0;i<lun(vc[py]);i++)gud[vc[py][i]]=z;
    }
    else if(!gd[px] && gd[py])
    {
        gd[px]=1;
        for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
    }
    for(i=0;i<lun(vc[py]);i++)
    {
        vc[px].pb(vc[py][i]);
        v[vc[py][i]].pb(mkp(px,z));
    }
    vc[py].clear();
    if(!gd[px] && !gd[py] && mx[px]>=3)
    {
        gd[px]=1;
        for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
    }
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
    n=N,m=M;
    for(i=0;i<m;i++)
    {
        U[i]++,V[i]++;
        g.pb(mkp(W[i],mkp(U[i],V[i])));
    }
    sort(all(g));
    for(i=1;i<=n;i++)
    {
        sz[i]=1;
        p[i]=i;
        v[i].pb(mkp(i,0));
        vc[i].pb(i);
    }
    for(i=0;i<m;i++)
    {
        x=g[i].sc.fr,y=g[i].sc.sc;
        uni(x,y,g[i].fr);
    }
}
int getMinimumFuelCapacity(int x,int y)
{
    x++,y++,rs=inf;
    if(!gud[x])return -1;
    for(i=0;i<lun(v[x]);i++)
    {
        vl=inf;
        for(j=0;j<lun(v[y]);j++)
        {
            if(v[x][i].fr==v[y][j].fr)
            {
                vl=max(v[x][i].sc,v[y][j].sc);
                break;
            }
        }
        rs=min(rs,vl);
    }
    rs=max(rs,max(gud[x],gud[y]));
    return rs;
}
/*int main()
{
    //freopen("sol.in","r",stdin);
    //freopen("sol.out","w",stdout);
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 0;
}*/

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