Submission #250819

# Submission time Handle Problem Language Result Execution time Memory
250819 2020-07-19T09:00:44 Z dvdg6566 Transport (COCI19_transport) C++14
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=310;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

ll A[MAXN];
vi tmin,tmout;

ll res(){
	sort(ALL(tmin));
	sort(ALL(tmout));
	// cerr<<"Query\n";
	// for(auto i:tmin)cerr<<i<<' ';cerr<<'\n';
	// for(auto i:tmout)cerr<<i<<' ';cerr<<'\n';
	ll X=0;
	ll ans=0;
	for(auto i:tmin){
		while(SZ(tmout)&&tmout.back()+i>=0){
			tmout.pop_back();++X;
		}
		ans+=X;
	}
	return ans;
}

ll out;

struct CD{
	vi par,ban,sub;
	vpi V[MAXN];
	ll N;
	vi allouts,allins;
	CD(ll _N):N(_N){
		par.resize(N,-1);
		ban.resize(N,-1);
		sub.resize(N,-1);
	}
	void build(ll u,ll p,ll l){
		ll n=dfs1(u,-1);
		ll cent=dfs2(u,-1,n);
		par[cent]=p;
		ban[cent]=l;
		// cerr<<"Cent "<<cent<<'\n';
		allouts.clear();allins.clear();
		ll X=-1;
		for(auto v:V[cent])if(ban[v.f]==-1){
			tmout.clear();tmin.clear();

			ll ds=A[cent]-v.s;
			ll r=A[v.f]-v.s;
			dfs3(v.f,cent,ds,min(0,ds),r);
			for(auto i:tmout)allouts.pb(i);
			for(auto i:tmin)allins.pb(i);
			ll t=res();
			// cerr<<"Sub "<<t<<'\n';
			X-=t;
		}
		tmout.clear();tmin.clear();
		tmin.pb(0);tmout.pb(0);
		for(auto i:allouts)tmout.pb(i);
		for(auto i:allins)tmin.pb(i);
		// cerr<<"Node "<<cent<<'\n';
		// for(auto i:tmout)cerr<<i<<' ';cerr<<'\n';
		// for(auto i:tmin)cerr<<i<<' ';cerr<<'\n';
		X += res();
		// cerr<<X<<'\n';
		out += X;

		for(auto v:V[cent])if(ban[v.f]==-1)build(v.f,cent,l+1);
	}
	ll dfs1(ll u,ll p){
		// ds is the current distance already completed
		sub[u]=1;
		for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
			sub[u]+=dfs1(v.f,u);
		}
		return sub[u];
	}
	ll dfs2(ll u,ll p,ll n){
		for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
			if(sub[v.f]>n/2)return dfs2(v.f,u,n);
		}
		return u;
	}
	void dfs3(ll u,ll p,ll ds,ll cs,ll req){
		tmout.pb(cs);
		tmin.pb(req);
		req=min(0,req);
		for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
			ll d=ds+A[u]-v.s;
			ll nr=req+A[v.f]-v.s;
			dfs3(v.f,u,d,min(cs,d),nr);
		}
	}
}*root;

ll N,a,b,w;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	root=new CD(N);
	for(ll i=0;i<N;++i)cin>>A[i];
	for(ll i=1;i<N;++i){
		cin>>a>>b>>w;--a;--b;
		root->V[a].pb(b,w);
		root->V[b].pb(a,w);
	}
	root->build(0,-1,0);
	cout<<out;
}

Compilation message

transport.cpp: In member function 'void CD::build(ll, ll, ll)':
transport.cpp:66:29: error: no matching function for call to 'min(int, ll&)'
    dfs3(v.f,cent,ds,min(0,ds),r);
                             ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 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 transport.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
transport.cpp:66:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
    dfs3(v.f,cent,ds,min(0,ds),r);
                             ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 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 transport.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
transport.cpp:66:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
    dfs3(v.f,cent,ds,min(0,ds),r);
                             ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
transport.cpp:66:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
    dfs3(v.f,cent,ds,min(0,ds),r);
                             ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
transport.cpp:66:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
    dfs3(v.f,cent,ds,min(0,ds),r);
                             ^
transport.cpp: In member function 'void CD::dfs3(ll, ll, ll, ll, ll)':
transport.cpp:103:16: error: no matching function for call to 'min(int, ll&)'
   req=min(0,req);
                ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 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 transport.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
transport.cpp:103:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
   req=min(0,req);
                ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 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 transport.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
transport.cpp:103:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
   req=min(0,req);
                ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
transport.cpp:103:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   req=min(0,req);
                ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
transport.cpp:103:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   req=min(0,req);
                ^