Submission #1225800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225800		KALARRY	Swapping Cities (APIO20_swap)	C++20	37 / 100	2098 ms	87688 KiB

swap

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int n,m,min_good[100005],s[100005],p[100005],deg[100005];
stack<int> cur_elem[100005];
bool is_good[100005];

int find_Sett(int i)
{
    if(p[i]==i)
        return p[i];
    p[i] = find_Sett(p[i]);
    return p[i];
}


bool is_Same_Sett(int i,int j)
{
    return find_Sett(i)==find_Sett(j);
}

void union_Sett(int i,int j,int w)
{
    int x = find_Sett(i);
    int y = find_Sett(j);
    deg[i]++;
    deg[j]++;
    if(deg[i] > 2)
        is_good[x] = true;
    if(deg[j] > 2)
        is_good[y] = true;
    if(is_Same_Sett(i,j))
        is_good[x] = true;
    else
    {
        if(s[x] < s[y])
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        is_good[x] |= is_good[y];
        if(cur_elem[y].size() > cur_elem[x].size())
            swap(cur_elem[x],cur_elem[y]);
        while(!cur_elem[y].empty())
        {
            int k = cur_elem[y].top();
            cur_elem[y].pop();
            cur_elem[x].push(k);
        }
    }
    if(is_good[x])
    {
        while(!cur_elem[x].empty())
        {
            int k = cur_elem[x].top();
            cur_elem[x].pop();
            min_good[k] = w;
        }
    }
}

pair<int,pair<int,int>> edges[200005];
vector<pair<int,int>> adj[200005];

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    for(int i = 1 ; i <= N ; i++)
    {
        p[i] = i;
        s[i] = 1;
        min_good[i] = -1;
        cur_elem[i].push(i);
    }
    for(int i = 1 ; i <= M ; i++)
        edges[i]  = {W[i-1],{V[i-1]+1,U[i-1]+1}};
    sort(edges+1,edges+M+1);
    for(int v,u,w,i = 1 ; i <= M ; i++)
    {
        v = edges[i].second.first;
        u = edges[i].second.second;
        w = edges[i].first;
        adj[v].push_back({u,w});
        adj[u].push_back({u,v});
        union_Sett(v,u,w);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int ret = min_good[X];
    if(ret==-1)
        return -1;
    for(int i = 1 ; i <= n ; i++)
    {
        p[i] = i;
        s[i] = 1;
    }
    sort(edges+1,edges+m+1);
    for(int v,u,w,i = 1 ; i <= m ; i++)
    {
        v = edges[i].second.first;
        u = edges[i].second.second;
        w = edges[i].first;
        union_Sett(v,u,w);
        ret = max(ret,w);
        if(is_Same_Sett(X,Y))
            break;
    }
    return ret;
}

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