Submission #1161575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161575		Aviansh	Swapping Cities (APIO20_swap)	C++20	100 / 100	117 ms	17072 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

struct dsu{
    vector<int>root;
    vector<int>siz;
    vector<int>valtime;
    vector<int>lastroot;
    vector<int>d;
    vector<vector<int>>g;
    int n;
    dsu(int nn){
        n=nn;
        root = vector<int>(n);
        iota(root.begin(),root.end(),0);
        siz=vector<int>(n,1);
        valtime = vector<int>(n,1e9);
        lastroot = vector<int>(n,-1);
        d=vector<int>(n);
        g=vector<vector<int>>(n);
    }
    void makeVal(int x, int tim){
        x=findRoot(x);
        valtime[x]=min(valtime[x],tim);
    }
    bool unite(int x, int y, int tim){
        x=findRoot(x);
        y=findRoot(y);
        //cout << "turned into " << x << " " << y << "\n";
        if(x==y){
            makeVal(x,tim);
            //cout << "cycle found\n";
            return 0;
        }
        if(siz[x]<siz[y]){
            //cout << "swapped\n";
            swap(x,y);
        }
        //x is greater now
        lastroot[y]=tim;
        //as soon as timth edge was added y ceased to be root so this is non inclusive
        siz[x]+=siz[y];
        root[y]=x;
        if(valtime[y]<1e9){
            //if y comp is valid then x is also now valid
            //cout << y << " was valid\n";
            makeVal(x,tim);
        }
        return 1;
    }
    int findRoot(int x){
        if(x==root[x]){
            return x;
        }
        return findRoot(root[x]);
    }

    void dfs(int st, int dep, int p){
        d[st]=dep;
        for(int i : g[st]){
            if(i==p){
                continue;
            }
            dfs(i,dep+1,st);
        }
    }

    void pre(){
        //ok so all should be connected now and must do precomp for depth and all
        int r = findRoot(0);
        //all god is root now so depth 0
        //first it is time to make the tree
        for(int i = 0;i<n;i++){
            if(i==r)
                continue;
            g[i].push_back(root[i]);
            g[root[i]].push_back(i);
        }
        //tree made now dfs
        dfs(r,0,-1);
        //ok so depths done which means pre over now must make main thingy
    }

    int bestTime(int x, int y){
        //TODO: will make corner case for -1s
        if(d[x]<d[y]){
            swap(x,y);
        }
        int ans = -1;
        while(d[x]>d[y]){
            ans=max(ans,lastroot[x]);
            x=root[x];
        }
        //ok now both at same depth
        while(x!=y){
            ans=max(ans,lastroot[x]);
            ans=max(ans,lastroot[y]);
            x=root[x];
            y=root[y];
        }
        //ok now minimum time for them to be connected is here now minimum time for validity is to be discovered
        //will only make x go up now
        while(valtime[x]==1e9){
            ans=max(ans,lastroot[x]);
            x=root[x];
        }
        //ok so now it should be valid so just max
        ans=max(ans,valtime[x]);
        return ans;
    }
};

vector<array<int,3>>edges;
int n,m;
bool val = 1;
dsu ds(1e5+5);
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n=N;
    m=M;
    for(int i = 0;i<m;i++){
        edges.push_back({W[i],U[i],V[i]});
    }
    sort(edges.begin(),edges.end());
    int d[n];
    fill(d,d+n,0);
    for(int i = 0;i<m;i++){
        int a = edges[i][1];
        int b = edges[i][2];
        //cout << "uniting " << a << " " << b << "\n";
        ds.unite(a,b,i);
        //cout << "united " << a << " " << b << "\n";
        d[a]++;
        d[b]++;
        if(d[a]>=3||d[b]>=3){
            ds.makeVal(a,i);
        }
    }
    ds.pre();
    val=(ds.valtime[ds.findRoot(0)]!=1e9);
}

int getMinimumFuelCapacity(int x, int y) {
    if(!val)
        return -1;
    return edges[ds.bestTime(x,y)][0];
}

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