Submission #925265

#	Time	Username	Problem	Language	Result	Execution time	Memory
925265		adhityamv	Swapping Cities (APIO20_swap)	C++17	7 / 100	131 ms	23128 KiB

swap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int INF=1000000000;
struct UFDS{
    int n;
    vector<vector<pii>> roots;
    vector<vector<int>> children;
    vector<int> siz;
    vector<int> unpath;
    vector<pii> pathpoints;
    UFDS(){
        n=0;
    }
    void dsinit(int nn){
        n=nn;
        for(int i=0;i<n;i++){
            vector<int> v;
            v.push_back(i);
            vector<pii> vv;
            vv.push_back(mp(i,0));
            roots.push_back(vv);
            children.push_back(v);
            siz.push_back(1);
            unpath.push_back(-1);
            pathpoints.push_back(mp(i,i));
        }
    }
    bool unite(int x,int y,int w){
        int ox=x,oy=y;
        x=roots[x].back().first;
        y=roots[y].back().first;
        if(x==y){
            if(unpath[x]==-1){
                unpath[x]=w;
            }
            return false;
        }
        if(siz[x]<siz[y]) swap(x,y);
        for(int i:children[y]){
            roots[i].push_back(mp(x,w));
            children[x].push_back(i);
        }
        siz[x]+=siz[y];
        if(unpath[x]==-1 && unpath[y]==-1){
            if((ox!=pathpoints[x].fi && ox!=pathpoints[x].se) || (oy!=pathpoints[y].fi && oy!=pathpoints[y].se)){
                unpath[x]=w;
            }
            else{
                pathpoints[x]=mp(pathpoints[x].fi+pathpoints[x].se-ox,pathpoints[y].fi+pathpoints[y].se-oy);
            }
        }
        if(unpath[x]==-1 && unpath[y]!=-1) unpath[x]=w;
        return true;
    }
};
UFDS ds;
bool ispath=false;
void init(int n,int m,vector<int> u,vector<int> v,vector<int> w){
    vector<pair<int,pii>> edges;
    for(int i=0;i<m;i++) edges.push_back(mp(w[i],mp(u[i],v[i])));
    sort(edges.begin(),edges.end());
    ds.dsinit(n);
    for(auto p:edges){
        ds.unite(p.se.fi,p.se.se,p.fi);
    }
    if(ds.unpath[ds.roots[0].back().fi]==-1) ispath=true;
}
int getMinimumFuelCapacity(int u,int v){
    if(ispath) return -1;
    int iu=ds.roots[u].size()-1;
    int iv=ds.roots[v].size()-1;
    while(ds.roots[u][iu].fi==ds.roots[v][iv].fi){
        iu--,iv--;
    }
    iu++,iv++;
    while(ds.unpath[ds.roots[u][iu].fi]==-1) iu++;
    return max(max(ds.roots[u][iu].se,ds.roots[v][iv].se),ds.unpath[ds.roots[u][iu].fi]);
}

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