Submission #645553

#	Time	Username	Problem	Language	Result	Execution time	Memory
645553		Tenis0206	Swapping Cities (APIO20_swap)	C++11	0 / 100	339 ms	44928 KiB

swap

#include <bits/stdc++.h>

using namespace std;

const int oo = INT_MAX;

vector<pair<int,int>> G[100005];
vector<pair<int,pair<int,int>>> e;

vector<int> l[100005];
vector<pair<int,int>> c[100005];

int t[100005];
int Max[100005];

multiset<int> s[100005];

int reprezentant(int nod)
{
    if(t[nod]==nod)
    {
        return nod;
    }
    return reprezentant(t[nod]);
}

void uneste(int x, int y, int cost)
{
    x = reprezentant(x);
    y = reprezentant(y);
    if(x==y)
    {
        return;
    }
    auto itx = s[x].lower_bound(cost);
    s[x].erase(itx);
    auto ity = s[y].lower_bound(cost);
    s[y].erase(ity);
    if(l[x].size() > l[y].size())
    {
        t[y] = x;
        for(auto it=s[y].begin();it!=s[y].end();it++)
        {
            s[x].insert(*it);
        }
        Max[x] = max(Max[x],cost);
        Max[x] = max(Max[x],Max[y]);
        auto it = s[x].begin();
        int val = 0;
        if(it==s[x].end())
        {
            val = oo;
        }
        else
        {
            val = *it;
        }
        val = max(val,Max[x]);
        for(auto it : l[y])
        {
            l[x].push_back(it);
            c[it].push_back({x,val});
        }
    }
    else
    {
        t[x] = y;
        for(auto it=s[x].begin();it!=s[x].end();it++)
        {
            s[y].insert(*it);
        }
        Max[y] = max(Max[y],cost);
        Max[y] = max(Max[y],Max[x]);
        auto it =s[y].begin();
        int val = 0;
        if(it==s[y].end())
        {
            val = oo;
        }
        else
        {
            val = *it;
        }
        val = max(val,Max[y]);
        for(auto it : l[x])
        {
            l[y].push_back(it);
            c[it].push_back({y,val});
        }
    }
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for(int i=0;i<m;i++)
    {
        int x = u[i];
        int y = v[i];
        int c = w[i];
        e.push_back({c,{x,y}});
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    sort(e.begin(),e.end());
    for(int i=0;i<n;i++)
    {
        t[i] = i;
        Max[i] = 0;
        for(auto it : G[i])
        {
            int c = it.second;
            s[i].insert(c);
        }
        auto it = s[i].begin();
        l[i].push_back(i);
        c[i].push_back({i,*it});
    }
    for(auto it : e)
    {
        int x = it.second.first;
        int y = it.second.second;
        int c = it.first;
        uneste(x,y,c);
    }
    for(int i=0;i<n;i++)
    {
        reverse(c[i].begin(),c[i].end());
    }
}

int getMinimumFuelCapacity(int x, int y)
{
    return -1;
    int st = 0;
    int dr = min(c[x].size(),c[y].size()) - 1;
    int poz = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(c[x][mij].first==c[y][mij].first)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    if(c[x][poz].second==oo || c[y][poz].second==oo)
    {
        return -1;
    }
    return max(c[x][poz].second,c[y][poz].second);
}

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