Submission #306684

#	Time	Username	Problem	Language	Result	Execution time	Memory
306684		azberjibiou	Swapping Cities (APIO20_swap)	C++17	100 / 100	606 ms	37788 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pii pair<int, int>
#define ll long long
using namespace std;
const int mxN=100010;
const int mxM=200020;
const int INF=1000000007;
typedef struct line{
    int s, e, val;
}line;
int N, M;
vector <line> lin;
vector <pii> col[mxN];
vector <int> Colp[mxN];
bool Chk[mxN];
int Pos[mxN];
int deg[mxN];
bool cmp1(line a, line b)
{
    return a.val<b.val;
}
bool cmp2(pii a, pii b)
{
    if(a.fir!=b.fir)    return a.fir<b.fir;
    return a.sec<b.sec;
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    N=n, M=m;
    lin.resize(M);
    for(int i=0;i<M;i++)    lin[i].s=U[i], lin[i].e=V[i], lin[i].val=W[i];
    sort(lin.begin(), lin.end(), cmp1);
    for(int i=0;i<N;i++)    col[i].push_back({0, i});
    for(int i=0;i<N;i++)    Colp[i].push_back(i);
    for(int i=0;i<M;i++)
    {
        int now1=lin[i].s, now2=lin[i].e, col1, col2;
        col1=col[now1].back().sec, col2=col[now2].back().sec;
        if(col1==col2)
        {
            if(Chk[col1])   continue;
            for(int ele : Colp[col1])
            {
                Pos[ele]=i+1;
            }
            Chk[col1]=true;
            continue;
        }
        bool can;
        if(Chk[col1] || Chk[col2])  can=true;
        else    can=false;
        if(can)
        {
            if(!Chk[col1])
            {
                for(int ele : Colp[col1])   Pos[ele]=i+1;
                Chk[col1]=true;
            }
            if(!Chk[col2])
            {
                for(int ele : Colp[col2])   Pos[ele]=i+1;
                Chk[col2]=true;
            }
        }
        else
        {
            if(deg[now1]>=2 || deg[now2]>=2)
            {
                for(int ele : Colp[col1])   Pos[ele]=i+1;
                for(int ele : Colp[col2])   Pos[ele]=i+1;
                Chk[col1]=Chk[col2]=true;
            }
        }
        if(Colp[col1].size()<Colp[col2].size())
        {
            for(int ele : Colp[col1])
            {
                col[ele].push_back({i+1, col2});
                Colp[col2].push_back(ele);
            }
        }
        else
        {
            for(int ele : Colp[col2])
            {
                col[ele].push_back({i+1, col1});
                Colp[col1].push_back(ele);
            }
        }
        deg[now1]++;
        deg[now2]++;
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if(col[X].back().sec!=col[Y].back().sec || Pos[X]==0 || Pos[Y]==0)    return -1;
    int s=0, e=M;
    while(s!=e)
    {
        int mid=(s+e)/2;
        pii tmp={mid, INF};
        int tmp1=lower_bound(col[X].begin(), col[X].end(), tmp, cmp2)-col[X].begin();
        int tmp2=lower_bound(col[Y].begin(), col[Y].end(), tmp, cmp2)-col[Y].begin();
        tmp1--;
        tmp2--;
        if(col[X][tmp1].sec!=col[Y][tmp2].sec)  s=mid+1;
        else    e=mid;
    }
    e=max(e, max(Pos[X], Pos[Y]));
    return lin[e-1].val;
}

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