Submission #1220438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220438		LeonidCuk	Swapping Cities (APIO20_swap)	C++20	36 / 100	890 ms	589824 KiB

swap

#include <bits/stdc++.h>
using namespace std;
class krt
{
    public:
    vector<vector<int>>lca,g;
    int timer=0,n,m;
    vector<int>dsu,res,en,et;
    vector<bool>moze;
    int vfind(int a)
    {
        if(a==dsu[a])return a;
        return dsu[a]=vfind(dsu[a]);
    }
    void dfs(int a,int b)
    {
        et[a]=timer;
        timer++;
        lca[a].push_back(b);
        for(int i=1;i<20;i++)
        {
            lca[a].push_back(lca[lca[a][i-1]][i-1]);
        }
        for(auto i:g[a])
        {
            dfs(i,a);
        }
        en[a]=timer-1;
    }
    bool check(int a,int b)
    {
        return et[a]<=et[b]&&en[b]<=en[a];
    }
    int findlca(int a,int b)
    {
        for(int i=19;i>=0;i--)
        {
            if(!check(lca[a][i],b))a=lca[a][i];
        }
        if(!check(a,b))a=lca[a][0];
        if(moze[a])return a;
        for(int i=19;i>=0;i--)
        {
            if(!moze[lca[a][i]])a=lca[a][i];
        }
        return lca[a][0];
    }
    krt(){}
    krt(int n1,int m1,vector<int>U,vector<int>V,vector<int>W)
    {
        m=m1;
        n=n1;
        en.resize(n+m);
        et.resize(n+m);
        res.resize(n+m);
        lca.resize(n+m);
        g.resize(n+m);
        dsu.resize(n+m);
        moze.resize(n+m);
        int a,b;
        vector<pair<int,int>>t;
        vector<int>deg(n);
        for(int i=0;i<m;i++)t.push_back({W[i],i});
        sort(t.begin(),t.end());
        for(int i=0;i<n;i++)
        {
            dsu[i]=i;
            res[i]=0;
        }
        for(int i=0;i<m;i++)
        {
            a=U[t[i].second];
            b=V[t[i].second];
            deg[a]++;
            deg[b]++;
            int a1=vfind(a);
            int b1=vfind(b);
            dsu[n+i]=n+i;
            dsu[a1]=n+i;
            dsu[b1]=n+i;
            res[n+i]=W[t[i].second];
            g[n+i].push_back(a1);
            g[n+i].push_back(b1);
            if(moze[a1]||moze[b1])moze[n+i]=true;
            if(a1==b1)moze[n+i]=true;
            if(deg[a]>2||deg[b]>2)moze[n+i]=true;

        }
        dfs(n+m-1,n+m-1);
    }
    int query(int a,int b)
    {
        if(moze[n+m-1]==false)return -1;
        return res[findlca(a,b)];
    }
};
krt drvo;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    drvo=krt(N,M,U,V,W);
}
int getMinimumFuelCapacity(int X, int Y) {
    return drvo.query(X,Y);
}

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