Submission #597245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
597245	2022-07-15T19:13:56 Z	Ozy	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define des first
#define w second
#define INF 1000000000

struct x{
    lli anc;
    lli mayor;
    lli seg;
};

//solucion arbol LCA
lli n,m,a,b,c;
lli prof[MAX+2],pp[MAX+2];
vector<pair<lli,lli> > hijos[MAX+2];
x lca[20][MAX+2];

x sube(lli a,lli b) {
    x res = {a,0,lca[0][a].seg};

    lli dif = prof[a] - prof[b];
    rep(i,0,18) {
        if (dif == 0) break;

        if (dif&1) {
            res.mayor = max(res.mayor, lca[i][res.anc]);
            res.seg = min(res.seg, lca[i][res.anc]);
            res.anc = lca[i][res.anc].anc;
        }

        dif /= 2;
    }

    return res;
}

void dfs(lli pos, lli padre,lli p,lli peso) {
    lli a = INF;
    lli b = INF;

    pp[pos] = peso;
    prof[pos] = p;
    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        if (h.w < a) {
            swap(a,b);
            a = h.w;
        }
        else if (h.w < b) b = h.w;
    }

    lca[0][pos] = {padre,peso,b};
    lli otro = padre;
    rep(i,1,18) {
        lca[i][pos].anc = lca[i - 1][ otro ].anc;
        lca[i][pos].mayor = max(lca[i-1][pos].mayor, lca[i-1][otro].mayor);
        if (lca[i-1][otro].seg == 0) lca[i-1][otro].seg = INF;
        lca[i][pos].seg = min(lca[i-1][pos].seg, lca[i-1][otro].seg);

        otro = lca[i][pos];
    }

    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        dfs(h.des,pos,p+1,h.w);
    }

}

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    rep(i,0,m-1) {
        a = U[i]+1;
        b = V[i]+1;
        c = W[i];

        hijos[a].push_back({b,c});
        hijos[b].push_back({a,c});
    }

    dfs(1,0,1,INF);

}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;

    if (prof[X] < prof[Y]) swap(X,Y);
    x act = sube(X,Y);

    if (act.anc != Y) {

    }

    act.seg = min(act.seg, lca[0][act.anc]);
    act.seg = min(act.seg, lca[0][act.anc]);

}

Compilation message

swap.cpp: In function 'x sube(long long int, long long int)':
swap.cpp:35:55: error: no matching function for call to 'max(long long int&, x&)'
   35 |             res.mayor = max(res.mayor, lca[i][res.anc]);
      |                                                       ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
swap.cpp:35:55: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
   35 |             res.mayor = max(res.mayor, lca[i][res.anc]);
      |                                                       ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
swap.cpp:35:55: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
   35 |             res.mayor = max(res.mayor, lca[i][res.anc]);
      |                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
swap.cpp:35:55: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   35 |             res.mayor = max(res.mayor, lca[i][res.anc]);
      |                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
swap.cpp:35:55: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   35 |             res.mayor = max(res.mayor, lca[i][res.anc]);
      |                                                       ^
swap.cpp:36:51: error: no matching function for call to 'min(long long int&, x&)'
   36 |             res.seg = min(res.seg, lca[i][res.anc]);
      |                                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
swap.cpp:36:51: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
   36 |             res.seg = min(res.seg, lca[i][res.anc]);
      |                                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
swap.cpp:36:51: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
   36 |             res.seg = min(res.seg, lca[i][res.anc]);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
swap.cpp:36:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   36 |             res.seg = min(res.seg, lca[i][res.anc]);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
swap.cpp:36:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   36 |             res.seg = min(res.seg, lca[i][res.anc]);
      |                                                   ^
swap.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
swap.cpp:69:26: error: cannot convert 'x' to 'long long int' in assignment
   69 |         otro = lca[i][pos];
      |                ~~~~~~~~~~^
      |                          |
      |                          x
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:106:43: error: no matching function for call to 'min(long long int&, x&)'
  106 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
swap.cpp:106:43: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
  106 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
swap.cpp:106:43: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
  106 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
swap.cpp:106:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  106 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
swap.cpp:106:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  106 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
swap.cpp:107:43: error: no matching function for call to 'min(long long int&, x&)'
  107 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
swap.cpp:107:43: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
  107 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from swap.h:1,
                 from swap.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
swap.cpp:107:43: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'x')
  107 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
swap.cpp:107:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  107 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from swap.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
swap.cpp:107:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  107 |     act.seg = min(act.seg, lca[0][act.anc]);
      |                                           ^
swap.cpp:109:1: warning: no return statement in function returning non-void [-Wreturn-type]
  109 | }
      | ^