Submission #213546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
213546	2020-03-26T05:38:29 Z	usachevd0	Valley (BOI19_valley)	C++14	Compilation error	0 ms	0 KB

valley

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define ll __int128
    #define debug(...) 42
#endif

const int maxN = 100005;
const ll INF64 = 4e17;
int N, S, Q, root;
vector< pair<int, ll> > G[maxN];
bool good[maxN];
int par[maxN];
int tin[maxN], tout[maxN];

ll ans[maxN];
vector<pii> qvtx[maxN];

int timer;
void dfs0(int v, int p = -1)
{
    par[v] = p;
    tin[v] = timer++;
    for (auto e : G[v])
    {
        int u = e.fi;
        if (u != p)
        {
            dfs0(u, v);
        }
    }
    tout[v] = timer - 1;
}

bool upper(int a, int b)
{
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

mt19937 rng(time(0));
struct Node
{
    int y;
    int v;
    ll f, down_m;
    ll s, down_s;
    int sz;
    Node *l, *r;

    Node() {}
    Node(int _v)
    {
        y = rng();
        v = _v;
        sz = 1;
        f = down_m = INF64;
        s = down_s = 0;
        down_s = 0;
        l = r = 0;
    }
};

int sz(Node *&t)
{
    return t ? t->sz : 0;
}

void upd(Node *&t)
{
    if (t)
    {
        t->sz = sz(t->l) + 1 + sz(t->r);
    }
}

void apply_m(Node *&t, ll x)
{
    if (t)
    {
        chkmin(t->f, x + t->s);
        chkmin(t->down_m, x);
    }
}

void apply_s(Node *&t, ll x)
{
    if (t)
    {
        t->s += x;
        t->down_s += x;
    }
}

void push(Node *&t)
{
    if (!t) return;
    if (t->down_s)
    {
        apply_s(t->l, t->down_s);
        apply_s(t->r, t->down_s);
        t->down_s = 0;
    }
    if (t->down_m < INF64)
    {
        apply_m(t->l, t->down_m);
        apply_m(t->r, t->down_m);
        t->down_m = INF64;
    }
}

Node* merge(Node *a, Node *b)
{
    if (!a) return b;
    if (!b) return a;
    if (a->y > b->y)
    {
        push(a);
        a->r = merge(a->r, b);
        upd(a);
        return a;
    }
    else
    {
        push(b);
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

ll gt(Node *t, int k)
{
    if (!t) return INF64;
    int szl = sz(t->l);
    if (k == szl)
        return t->f;
    push(t);
    if (k < szl)
        return gt(t->l, k);
    else
        return gt(t->r, k - szl - 1);
}

/*
void Tdebug(Node *t)
{
    if (t)
    {
        push(t);
        Tdebug(t->l);
        cout << t->v << '|' << t->f << ' ';
        Tdebug(t->r);
    }
}*/

pair<Node*, ll> dfs1(int v, int p = -1)
{
    Node* T = new Node(v);
    ll closest_down = INF64;
    if (good[v])
    {
        apply_m(T, 0);
        closest_down = 0;
    }
    for (auto e : G[v])
    {
        int u = e.fi;
        ll c = e.se;
        if (u != p)
        {
            auto res = dfs1(u, v);
            auto Q = res.fi;
            ll cd = res.se + c;
            apply_m(T, cd);
            apply_s(Q, c);
            apply_m(Q, closest_down);
            T = merge(T, Q);
            chkmin(closest_down, cd);
        }
    }
    for (pii q : qvtx[v])
    {
        int u = q.fi;
        int idx = q.se;
        int pos = tin[u] - tin[v];
        ans[idx] = gt(T, pos);
    }
//    debug(v, closest_down); Tdebug(T); cout << endl;
    return {T, closest_down};
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S >> Q >> root;
    pii edges[N - 1];
    for (int i = 0; i < N - 1; ++i)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
        edges[i] = {a, b};
    }
    while (S--)
    {
        int v;
        cin >> v;
        good[v] = true;
    }
    dfs0(root);
    fill(ans, ans + Q, INF64);
    for (int i = 0; i < Q; ++i)
    {
        int ei, u;
        cin >> ei >> u;
        --ei;
        int v = edges[ei].fi == par[edges[ei].se] ? edges[ei].se : edges[ei].fi;
        if (!upper(v, u))
        {
            ans[i] = -1;
            continue;
        }
        qvtx[v].emplace_back(u, i);
    }
    dfs1(root);
    for (int i = 0; i < Q; ++i)
    {
        if (ans[i] == -1)
        {
            cout << "escaped\n";
        }
        else if (ans[i] >= INF64)
        {
            cout << "oo\n";
        }
        else
        {
            cout << ans[i] << '\n';
        }
    }

    return 0;
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:275:18: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream {aka std::basic_ostream<char>}' and '__int128')
             cout << ans[i] << '\n';
             ~~~~~^~~~~~~~~
In file included from /usr/include/c++/7/istream:39:0,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from valley.cpp:1:
/usr/include/c++/7/ostream:166:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long __n)
       ^~~~~~~~
/usr/include/c++/7/ostream:170:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned long __n)
       ^~~~~~~~
/usr/include/c++/7/ostream:174:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(bool __n)
       ^~~~~~~~
In file included from /usr/include/c++/7/ostream:693:0,
                 from /usr/include/c++/7/istream:39,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from valley.cpp:1:
/usr/include/c++/7/bits/ostream.tcc:91:5: note: candidate: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]
     basic_ostream<_CharT, _Traits>::
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/istream:39:0,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from valley.cpp:1:
/usr/include/c++/7/ostream:181:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned short __n)
       ^~~~~~~~
In file included from /usr/include/c++/7/ostream:693:0,
                 from /usr/include/c++/7/istream:39,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from valley.cpp:1:
/usr/include/c++/7/bits/ostream.tcc:105:5: note: candidate: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]
     basic_ostream<_CharT, _Traits>::
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/istream:39:0,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from valley.cpp:1:
/usr/include/c++/7/ostream:192:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned int __n)
       ^~~~~~~~
/usr/include/c++/7/ostream:201:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long long __n)
       ^~~~~~~~
/usr/include/c++/7/ostream:205:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned long long __n)
       ^~~~~~~~
/usr/include/c++/7/ostream:220:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(double __f)
       ^~~~~~~~
/usr/include/c++/7/ostream:224:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(float __f)
       ^~~~~~~~
/usr/include/c++/7/ostream:232:7: note: candidate: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long double __f)
       ^~~~~~~~
/usr/include/c++/7/ostream:519:5: note: candidate: std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]
     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
     ^~~~~~~~
/usr/include/c++/7/ostream:514:5: note: candidate: std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]
     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
     ^~~~~~~~
/usr/include/c++/7/ostream:508:5: note: candidate: std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]
     operator<<(basic_ostream<char, _Traits>& __out, char __c)
     ^~~~~~~~
/usr/include/c++/7/ostream:502:5: note: candidate: std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]
     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
     ^~~~~~~~