Submission #348583

#	Time	Username	Problem	Language	Result	Execution time	Memory
348583		denkendoemeer	Swapping Cities (APIO20_swap)	C++14	100 / 100	370 ms	38152 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"
#define ll long long
const int inf=1e9;
using namespace std;
vector<pair<int,pair<int,int>>>ed;
vector<pair<int,int>>dsu[100005];
int ans[100005],t[100005];
vector<int>g[100005];
void init(int n,int m,vector<int>x,vector<int>y,vector<int>w)
{
    int i;
    for(i=0;i<n;i++)
        ans[i]=inf;
    for(i=0;i<n;i++){
        dsu[i].push_back({0,i});
        g[i].push_back(i);
    }
    for(i=0;i<m;i++)
        ed.push_back({w[i],{y[i],x[i]}});
    sort(ed.begin(),ed.end());
    for(auto &it:ed){
        int y,x,w;
        y=it.second.first;
        x=it.second.second;
        w=it.first;
        int ty=dsu[y].back().second,tx=dsu[x].back().second;
        if (ty==tx){
            ans[ty]=min(ans[ty],w);
            continue;
        }
        ++t[y];
        ++t[x];
        if (g[ty].size()>g[tx].size())
            swap(tx,ty),swap(x,y);
        ans[tx]=min(ans[tx],max(w,ans[ty]));
        if (t[x]>=3 || t[y]>=3)
            ans[tx]=min(ans[tx],w);
        for(auto it2:g[ty]){
            g[tx].push_back(it2);
            dsu[it2].push_back({w,tx});
        }
    }
}
int getMinimumFuelCapacity(int x,int y)
{
    int tx=dsu[x].size()-1,ty=dsu[y].size()-1;
    int rez=inf,mini=inf;
    while(tx>=0 && ty>=0 && dsu[x][tx].second==dsu[y][ty].second){
        rez=max(dsu[x][tx].first,dsu[y][ty].first);
        mini=min(mini,max(rez,ans[dsu[x][tx].second]));
        tx--;
        ty--;
    }
    rez=max(rez,mini);
    if (rez==inf)
        return -1;
    return rez;
}

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