Submission #641344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641344	2022-09-16T13:51:41 Z	sumit_kk10	Harbingers (CEOI09_harbingers)	C++17	Compilation error	0 ms	0 KB

harbingers

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int __int128
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;
vector<pair<int, int> > g[N];
int n, par[N], dis[N], dp[N], s[N], d[N];
bool vis[N];

 
struct Line{
    int m, c;
 
    int val(int x){
        return m*x + c;
    }
};
 
vector<pair<Line, int> > hulls;
vector<pair<Line, int> > removed[N];
 
bool check(Line a, Line b, Line cc){
    int x = (b.c - a.c);
    x = x * (a.m - cc.m);
    int y = (cc.c - a.c);
    y = y * (a.m - b.m);
    if(x > y)
        return true;
    return false;
}
 
void insert(int mm, int cc, int node){
    Line cur;
    cur.m = mm;
    cur.c = cc;
    if(!hulls.empty() and hulls.back().F.m == mm){
        if(hulls.back().F.c > cc){
            vis[hulls.back().S] = false;
            removed[node].pb(hulls.back());
            hulls.pop_back();
        }
        else{
            vis[node] = false;
            return;
        }
    }
    while(hulls.size() > 1){
        if(check(hulls[hulls.size() - 2].F, hulls.back().F, cur)){
            vis[hulls.back().S] = false;
            removed[node].pb(hulls.back());
            hulls.pop_back();
        }
        else
            break;
    }
    reverse(removed[node].begin(), removed[node].end());
    hulls.pb({cur, node});
}

void insertt(int mm, int cc, int node){
    Line cur;
    cur.m = mm;
    cur.c = cc;
    if(!hulls.empty() and hulls.back().F.m == mm){
        if(hulls.back().F.c > cc){
            vis[hulls.back().S] = false;
            hulls.pop_back();
        }
        else{
            vis[node] = false;
            return;
        }
    }
    while(hulls.size() > 1){
        if(check(hulls[hulls.size() - 2].F, hulls.back().F, cur)){
            vis[hulls.back().S] = false;
            hulls.pop_back();
        }
        else
            break;
    }
    hulls.pb({cur, node});
}
 
int get(int x){
    if(hulls.empty())
        return 1e15;
    int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1;
    while(low <= high){
        int mid = (low + high) / 2;
        if(hulls[mid].F.val(x) <= hulls[mid + 1].F.val(x)){
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return hulls[ans].F.val(x);
}
 
void dfs(int node, int p, int sum){
    dis[node] = sum;
    par[node] = p;
    for(auto k : g[node]){
        if(k.F == p) continue;
        dfs(k.F, node, sum + k.S);
    }
}
 
void dfs1(int node){
    int mn = s[node] + dis[node] * d[node];
    int x = get(d[node]);
    if(x != 1e15)
        mn = min(mn, x + s[node] + dis[node] * d[node]);
    dp[node] = mn;
    if(node != 1){
        vis[node] = true;
        insert(-dis[node], dp[node], node);
    }
    for(auto k : g[node]){
        if(k.F == par[node]) continue;
        dfs1(k.F);
    }
    if(!hulls.empty() and vis[node])
        hulls.pop_back();
    for(auto k : removed[node]){
        vis[k.S] = true;
        insertt(k.F.m, k.F.c, k.S);
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    for(int i = 1; i < n; ++i)
        cin >> s[i + 1] >> d[i + 1];
    dfs(1, 0, 0);
    dfs1(1);
    for(int i = 2; i <= n; ++i)
        cout << dp[i] << " ";
}
 
int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Compilation message

harbingers.cpp: In function 'void solve()':
harbingers.cpp:136:9: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and '__int128')
  136 |     cin >> n;
      |     ~~~ ^~ ~
      |     |      |
      |     |      __int128
      |     std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:120:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  120 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:120:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
  136 |     cin >> n;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:124:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]' (near match)
  124 |       operator>>(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:124:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)' {aka 'std::basic_ios<char>& (*)(std::basic_ios<char>&)'} [-fpermissive]
  136 |     cin >> n;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:131:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  131 |       operator>>(ios_base& (*__pf)(ios_base&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:131:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: invalid conversion from '__int128' to 'std::ios_base& (*)(std::ios_base&)' [-fpermissive]
  136 |     cin >> n;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:168:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:168:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:172:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:172:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'short int&' to an rvalue of type 'short int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:175:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:175:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to an rvalue of type 'short unsigned int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:179:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:179:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:182:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:182:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'unsigned int&' to an rvalue of type 'unsigned int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:186:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  186 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:186:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'long int&' to an rvalue of type 'long int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:190:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  190 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:190:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to an rvalue of type 'long unsigned int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:195:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  195 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:195:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:199:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to an rvalue of type 'long long unsigned int'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:214:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  214 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:214:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'float&' to an rvalue of type 'float'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:218:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  218 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:218:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:222:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  222 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:222:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: cannot bind non-const lvalue reference of type 'long double&' to an rvalue of type 'long double'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:235:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  235 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/10/istream:235:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: invalid conversion from '__int128' to 'void*' [-fpermissive]
  136 |     cin >> n;
      |            ^
      |            |
      |            __int128
harbingers.cpp:136:12: error: cannot bind rvalue '(void*)((long int)n)' to 'void*&'
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/istream:259:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>]' (near match)
  259 |       operator>>(__streambuf_type* __sb);
      |       ^~~~~~~~
/usr/include/c++/10/istream:259:7: note:   conversion of argument 1 would be ill-formed:
harbingers.cpp:136:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__streambuf_type*' {aka 'std::basic_streambuf<char>*'} [-fpermissive]
  136 |     cin >> n;
      |            ^
      |            |
      |            __int128
harbingers.cpp:136:9: note: candidate: 'operator>>(int, __int128)' (built-in)
  136 |     cin >> n;
      |     ~~~~^~~~
harbingers.cpp:136:9: note:   no known conversion for argument 1 from 'std::istream' {aka 'std::basic_istream<char>'} to 'int'
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
                 from harbingers.cpp:1:
/usr/include/c++/10/cstddef:130:5: note: candidate: 'template<class _IntegerType> constexpr std::__byte_op_t<_IntegerType> std::operator>>(std::byte, _IntegerType)'
  130 |     operator>>(byte __b, _IntegerType __shift) noexcept
      |     ^~~~~~~~
/usr/include/c++/10/cstddef:130:5: note:   template argument deduction/substitution failed:
harbingers.cpp:136:5: note:   cannot convert 'std::cin' (type 'std::istream' {aka 'std::basic_istream<char>'}) to type 'std::byte'
  136 |     cin >> n;
      |     ^~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1476 |     operator>>(basic_istream<_CharT, _Traits>& __in,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note:   template argument deduction/substitution failed:
harbingers.cpp:136:12: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and '__int128'
  136 |     cin >> n;
      |            ^
In file included from /usr/include/c++/10/istream:991,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/