Submission #1161567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161567		Aviansh	Swapping Cities (APIO20_swap)	C++20	37 / 100	2094 ms	8324 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;
    dsu(int n){
        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);
    }
    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]);
    }
};

vector<array<int,3>>edges;
int n,m;
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 getMinimumFuelCapacity(int x, int y) {
    int d[n];
    fill(d,d+n,0);
    dsu ds(n);
    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);
        }
        if(ds.findRoot(x)==ds.findRoot(y)&&ds.valtime[ds.findRoot(x)]<1e9){
            return edges[i][0];
        }
    }
    return -1;
}

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