Submission #672628

#	Time	Username	Problem	Language	Result	Execution time	Memory
672628		Hanksburger	Swapping Cities (APIO20_swap)	C++17	13 / 100	115 ms	13532 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)
{
//    cout << "init\n";
    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;
//        cout << "par[" << x << "]=" << y << '\n';
        sz[y]+=sz[x];
        w1[x]=z;
        if (bridge)
            w2[y]=min(w2[y], z);
    }
//    cout << "initend\n";
}
int getMinimumFuelCapacity(int x, int y)
{
    int ans=0;
    while (x!=y)
    {
//        cout << "x y " << x << ' ' << y << '\n';
//        cout << "w1[x] w1[y] " << w1[x] << ' ' << w1[y] << '\n';
        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: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27