Submission #657862

#	Time	Username	Problem	Language	Result	Execution time	Memory
657862		activedeltorre	Swapping Cities (APIO20_swap)	C++14	100 / 100	1668 ms	106780 KiB

swap

#include "swap.h"
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
vector<pair<int,pair<int,int> > >edges;
bool cmp(pair<int,pair<int,int> >a,pair<int,pair<int,int> >b)
{
    return a.first<b.first;
}
vector<pair<long long,long long> >adj[200005];
long long backedge[200005];
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
vector<long long>vec;
long long inf=1e14;
void dfs(int curr,int parent)
{
    int i,k;
    lvl[curr]=lvl[parent]+1;
    vec.clear();
    jos[curr]=inf;
    if(adj[curr].size()>=3)
    {
        for(i=0; i<adj[curr].size(); i++)
        {
            vec.push_back(adj[curr][i].second);
        }
        sort(vec.begin(),vec.end());
        jos[curr]=vec[2];
    }
    if(backedge[curr]!=0)
    {
        jos[curr]=min(jos[curr],backedge[curr]);
    }
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=parent)
        {
            dfs(k,curr);
        }
        jos[curr]=min(jos[curr],max(jos[k],adj[curr][i].second));
    }
}
void dfs2(int curr,int par,long long val)
{
    long long i,k;
    sus[curr]=max(min(jos[par],sus[par]),val);
    rasp[curr]=min(sus[curr],jos[curr]);
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=par)
        {
            dfs2(k,curr,adj[curr][i].second);
        }
    }
}
///bl e parinte
/// drum e cost de a merge la parinte
/// ext e cost minim degreee 3
long long bl[33][200005];
long long ext[33][200005];
long long drum[33][200005];
int sef[200005];
void dfs3(int curr,int par,long long val)
{
    long long i,k;
    bl[0][curr]=par;
    ext[0][curr]=min(rasp[par],rasp[curr]);
    drum[0][curr]=val;
    for(i=1; i<=30; i++)
    {
        bl[i][curr]=bl[i-1][bl[i-1][curr]];
        ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]);
        drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
    }
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=par)
        {
            dfs3(k,curr,adj[curr][i].second);
        }
    }
}
int lca (long long a,long long b)
{
    long long i,curr;
    if(lvl[a]<lvl[b])
    {
        swap(a,b);
    }
    for(i=30; i>=0; i--)
    {
        curr=bl[i][a];
        if(lvl[curr]>=lvl[b])
        {
            a=curr;
        }
    }
    if(a==b)
    {
        return a;
    }
    else
    {
        for(i=30; i>=0; i--)
        {
            if(bl[i][a]!=bl[i][b])
            {
                a=bl[i][a];
                b=bl[i][b];
            }
        }
        return bl[0][a];
    }
}
pair<long long,long long> calc (int a,int b)
{
    long long curr,maxdrum=0,minrel=inf,i;
    if(a==b)
    {
        return make_pair(0,rasp[a]);
    }
    minrel=min(rasp[a],rasp[b]);
    maxdrum=drum[0][a];
    for(i=30; i>=0; i--)
    {
        curr=bl[i][a];
        if(lvl[curr]>=lvl[b])
        {
            maxdrum=max(maxdrum,drum[i][a]);
            minrel=min(minrel,ext[i][a]);
            a=curr;
        }
    }
    return make_pair(maxdrum,minrel);
}
int find (int u)
{
    if(sef[u]==u)
    {
        return u;
    }
    return sef[u]=find(sef[u]);
}
int merge (int a,int b)
{
    a=find(a);
    b=find(b);
    if(a!=b)
    {
        sef[a]=b;
        return 1;
    }
    return 0;
}
void init(int n, int m,vector<int> a, vector<int> b, vector<int> w)
{
    int i,x,y;
    long long val;
    for(i=1;i<=n;i++)
    {
        sef[i]=i;
    }
    for(i=1; i<=m; i++)
    {
        a[i-1]++;
        b[i-1]++;
        edges.push_back({w[i-1],{a[i-1],b[i-1]}});
    }
    sort(edges.begin(),edges.end(),cmp);
    for(i=0; i<m; i++)
    {
        val=edges[i].first;
        x=edges[i].second.first;
        y=edges[i].second.second;
        if(merge(x,y)==1)
        {
            adj[x].push_back({y,val});
            adj[y].push_back({x,val});
        }
        else
        {
            if(backedge[x]==0)
            {
                backedge[x]=val;
            }
            else
            {
                backedge[x]=min(backedge[x],val);
            }
            if(backedge[y]==0)
            {
                backedge[y]=val;
            }
            else
            {
                backedge[y]=min(backedge[y],val);
            }
        }
    }
    sus[0]=inf;
    jos[0]=inf;
    dfs(1,0);
    dfs2(1,0,0);
    dfs3(1,0,0);
}

int getMinimumFuelCapacity(int x, int y)
{
    long long lc;
    x++;
    y++;
    pair<long long,long long>a;
    pair<long long,long long>b;
    lc=lca(x,y);
    a=calc(x,lc);
    b=calc(y,lc);
    a.first=max(a.first,b.first);
    a.second=min(a.second,b.second);
    a.first=max(a.first,a.second);
    if(a.first==inf)
    {
        return -1;
    }
    else
    {
        return a.first;
    }
}
/*int main()
{
    int N, M;
    cin>>N>>M;
    vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i)
    {
        cin>>U[i]>>V[i]>>W[i];
    }
    int Q;
    cin>>Q;
    vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i)
    {
        cin>>X[i]>>Y[i];
    }
    init(N, M, U, V, W);
    vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i)
    {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }
    for (int i = 0; i < Q; ++i)
    {
        cout<<minimum_fuel_capacities[i]<<'\n';
    }
    return 0;
}*/

Compilation message (stderr)

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(i=0; i<adj[curr].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
swap.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs2(int, int, long long int)':
swap.cpp:55:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs3(int, int, long long int)':
swap.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~

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