Submission #657839

#	Time	Username	Problem	Language	Result	Execution time	Memory
657839		activedeltorre	Swapping Cities (APIO20_swap)	C++14	7 / 100	1241 ms	524288 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<int,long long> >adj[200005];
vector<long long>vec;
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
long long inf=1e14;
void dfs(int curr,int parent)
{
    int i,k;
    lvl[curr]=lvl[parent]+1;
    vec.clear();
    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];
    }
    else
    {
        jos[curr]=inf;
    }
    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[curr],adj[curr][i].second));
    }
}
void dfs2(int curr,int par,long long val)
{
    int 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];
void dfs3(int curr,int par,long long val)
{
    int 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 (int a,int b)
{
    int 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;
    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);
}
void init(int n, int m,vector<int> a, vector<int> b, vector<int> w)
{
    int i;
    for(i=1; i<=m; i++)
    {
        a[i-1]++;
        b[i-1]++;
        adj[a[i-1]].push_back({b[i-1],w[i-1]});
        adj[b[i-1]].push_back({a[i-1],w[i-1]});
        //  edges.push_back({w[i-1],{a[i-1],b[i-1]}});
    }
    // sort(edges.begin(),edges.end(),cmp);
    sus[0]=inf;
    jos[0]=inf;
    dfs(1,0);
    dfs2(1,0,0);
    dfs3(1,0,0);
}

int getMinimumFuelCapacity(int x, int y)
{
    int 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,b.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:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(i=0; i<adj[curr].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
swap.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs2(int, int, long long int)':
swap.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs3(int, int, long long int)':
swap.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~

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