Submission #672630

#	Time	Username	Problem	Language	Result	Execution time	Memory
672630		Hanksburger	Swapping Cities (APIO20_swap)	C++17	100 / 100	151 ms	11228 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int deg[100005], par[100005], sz[100005], w1[100005], w2[100005];
vector<pair<int, pair<int, int> > > edge;
int findPar(int x)
{
    return (par[x]==x)?x:findPar(par[x]);
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for (int i=0; i<m; i++)
        edge.push_back({w[i], {u[i], v[i]}});
    sort(edge.begin(), edge.end());
    for (int i=0; i<n; i++)
    {
        par[i]=i;
        sz[i]=1;
        w1[i]=w2[i]=2e9;
    }
    for (int i=0; i<m; i++)
    {
        int x=edge[i].second.first, y=edge[i].second.second, z=edge[i].first;
        bool bridge=(deg[x]>=2 || deg[y]>=2);
        deg[x]++;
        deg[y]++;
        x=findPar(x);
        y=findPar(y);
        if (x==y)
        {
            w2[y]=min(w2[y], z);
            continue;
        }
        if (sz[x]>sz[y])
            swap(x, y);
        par[x]=y;
        sz[y]+=sz[x];
        w1[x]=z;
        if (bridge || w2[x]<2e9)
            w2[y]=min(w2[y], z);
    }
}
int getMinimumFuelCapacity(int x, int y)
{
    int ans=0;
    while (x!=y)
    {
        if (w1[x]<w1[y])
        {
            ans=w1[x];
            x=par[x];
        }
        else
        {
            ans=w1[y];
            y=par[y];
        }
    }
    while (par[x]!=x)
    {
        if (w2[x]<2e9)
            return max(ans, w2[x]);
        ans=w1[x];
        x=par[x];
    }
    if (w2[x]<2e9)
        return max(ans, w2[x]);
    return -1;
}

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