Submission #891982

#	Time	Username	Problem	Language	Result	Execution time	Memory
891982		vjudge1	Two Currencies (JOI23_currencies)	C++17	Compilation error	0 ms	0 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;



struct Fenwick{
	int n;
	vector<int> fenw;
	Fenwick(int sz){
		n = sz;
		fenw.resize(n+1, 0);
	};
	
	void add(int i, int x){
		for(; i <= n; i+= i&-i){
			fenw[i]+= x;
		}
	}
	
	int pref(int i){
		int s = 0;
		for(; i > 0; i-= i & -i){
			s+= fenw[i];
		}
		return s;
	}
	int sum(int l, int r){
		return pref(r) - pref(l-1);
	}
};
int n, m, q;
vector<int > g[N+10];
vector< pair<int, int> > edge;
int depth[N+10], up[N+10][20], sum[N+10][20];
int tin[N+10], tout[N+10], timer = 1;
void dfs(int v, int par){
	tin[v] = timer++;
	up[v][0] = par;
	for(int to : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		dfs(to, v);
	}
	tout[v] = timer - 1;
}
int lca(int a, int b){
	if(depth[b] < depth[a]) swap(a, b);
	int k = depth[b] - depth[a];
	for(int i = 0;i < 20; i++){
		if(k & (1<<i)) b = up[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i--){
		if(up[b][i] != up[a][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}


int ones(int a, int d){
	int s = 0;
	for(int i = 0;i < 20; i++){
		if(d & (1<<i)){
			s+= sum[a][i];
			a = up[a][i];
		}
	}
	return s;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		edge.push_back({a, b});
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	vector<array<int, 2> > adds;
	for(int i = 0;i < m; i++){
		int p, c; cin >> p >> c;
		int a = edge[p-1].ff, b = edge[p-1].ss;
		if(depth[a] < depth[b]) swap(a, b);
		adds.push_back({a, c});
		sum[a][0]+= 1;
	}
	sort(all(adds), [&](auto A, auto B){
		return A[1] < B[1];
	});
	for(int j = 1;j < 20; j++){
		for(int i = 1;i <= n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1];
		}
	}
	int s, t, x, y;
	vector<array<int, 4> > query(q);
	vector<int> overall lc;
	vector<vector<int> > rn(q, vector<int>(2, {0, m+1}));
	for(auto &A : query){
		cin >> A[0] >> A[1] >> A[2] >> A[3];
		int all_p = lca(A[0], A[1]);
		lc.push_back(all_p);
		int checkpoints = ones(A[0],  depth[A[0]] -depth[lc]) + ones(A[1], depth[A[1]] - depth[lc]);
		overall.push_back(checkpoints);
	}
	vector<int> ans(q);
	for(int i = 0;i < q; i++){
		ans[i] = A[2] - overall[i];
	}
	while(true){
		Fenwick f1(n + 1), f2(n + 1);
		vector< vector<int> > middles(m + 1);
		bool finish = true;
		for(int i = 0;i < q; i++){
			if(rn[i][0] + 1 < rn[i][1]){
				int mid = (rn[i][0] + rn[i][1]) / 2;
				middles[mid].push_back(i);
				finish = false;
			}
		}
		
		for(int i = 0;i <= m; i++){
			auto [a, c] = adds[i];
			f1.add(tin[a], c);
			f1.add(tout[a] + 1, -c);
			f2.add(tin[a], 1);
			f2.add(tout[a] + 1, -1);
			for(int idx : middles[i]){
				
			}
			
		}
		
		
		
		
		
		
		if(finish) break;
	}
	for(int i = 0;i < q; i++) cout << ans[i] << '\n';
	
	auto good=[&](int mid){
		Fenwick f1(n + 1), f2(n + 1);
		int idx = 0;
		for(auto [a, c] : adds){
			f1.add(tin[a], c);
			f1.add(tout[a] + 1, -c);
			f2.add(tin[a], 1);
			f2.add(tout[a] + 1, -1);
			if(idx == mid) break;
			idx++;
		}
		int sum = f1.pref(tin[s]) + f1.pref(tin[t]) - 2 * f1.pref(tin[lc]);
		int cnt = f2.pref(tin[s]) + f2.pref(tin[t]) - 2 * f2.pref(tin[lc]);
		return make_pair(sum, cnt);
	};
	
	
	
	while(q--){
		cin >> s >> t >> x >> y;
		int l = 0, r = m + 1;
		lc = lca(s, t);
		int checkpoints = ones(s,  depth[s] -depth[lc]) + ones(t, depth[t] - depth[lc]);
	//	cout << "overall there were : " << checkpoints << "\n";
		while(l + 1 < r){
			int mid = (l + r)>>1;
			pair<int, int> ch = good(mid);
			if(ch.ff <= y) l = mid;
			else r = mid;
		}
		
		if(good(l).ff > y){
			cout << max(-1LL, x - checkpoints) << '\n';
			continue;
		}
		
		pair<int, int> ch = good(l);
	//	cout << ch.ss << " = ";
		checkpoints-= ch.ss;
		cout << max(-1LL, x - checkpoints) << '\n';
	}
	
	
	return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:112:22: error: expected initializer before 'lc'
  112 |  vector<int> overall lc;
      |                      ^~
currencies.cpp:113:52: error: no matching function for call to 'std::vector<long long int>::vector(int, <brace-enclosed initializer list>)'
  113 |  vector<vector<int> > rn(q, vector<int>(2, {0, m+1}));
      |                                                    ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from currencies.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:653:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
  653 |  vector(_InputIterator __first, _InputIterator __last,
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:653:2: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from currencies.cpp:1:
/usr/include/c++/10/bits/stl_iterator_base_types.h: In substitution of 'template<class _InIter> using _RequireInputIter = std::__enable_if_t<std::is_convertible<typename std::iterator_traits< <template-parameter-1-1> >::iterator_category, std::input_iterator_tag>::value> [with _InIter = int]':
/usr/include/c++/10/bits/stl_vector.h:652:9:   required from here
/usr/include/c++/10/bits/stl_iterator_base_types.h:249:11: error: no type named 'iterator_category' in 'struct std::iterator_traits<int>'
  249 |     using _RequireInputIter =
      |           ^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from currencies.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:625:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  625 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:625:43: note:   no known conversion for argument 1 from 'int' to 'std::initializer_list<long long int>'
  625 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:607:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:607:23: note:   no known conversion for argument 1 from 'int' to 'std::vector<long long int>&&'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |              ~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_vector.h:589:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::false_type = std::integral_constant<bool, false>]'
  589 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:589:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/10/bits/stl_vector.h:585:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>; std::true_type = std::integral_constant<bool, true>]'
  585 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:585:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/10/bits/stl_vector.h:575:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:575:28: note:   no known conversion for argument 1 from 'int' to 'const std::vector<long long int>&'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:572:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  572 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:572:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:553:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  553 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:553:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:522:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const value_type&, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  522 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:522:47: note:   no known conversion for argument 2 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const long long int&'}
  522 |       vector(size_type __n, const value_type& __value,
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~
/usr/include/c++/10/bits/stl_vector.h:510:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:510:51: note:   no known conversion for argument 2 from '<brace-enclosed initializer list>' to 'const allocator_type&' {aka 'const std::allocator<long long int>&'}
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:497:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:497:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:487:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector() [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  487 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:487:7: note:   candidate expects 0 arguments, 2 provided
currencies.cpp:117:3: error: 'lc' was not declared in this scope; did you mean 'lca'?
  117 |   lc.push_back(all_p);
      |   ^~
      |   lca
currencies.cpp:119:3: error: 'overall' was not declared in this scope
  119 |   overall.push_back(checkpoints);
      |   ^~~~~~~
currencies.cpp:123:12: error: 'A' was not declared in this scope
  123 |   ans[i] = A[2] - overall[i];
      |            ^
currencies.cpp:123:19: error: 'overall' was not declared in this scope
  123 |   ans[i] = A[2] - overall[i];
      |                   ^~~~~~~
currencies.cpp:143:12: warning: unused variable 'idx' [-Wunused-variable]
  143 |    for(int idx : middles[i]){
      |            ^~~
currencies.cpp: In lambda function:
currencies.cpp:169:65: error: 'lc' was not declared in this scope; did you mean 'lca'?
  169 |   int sum = f1.pref(tin[s]) + f1.pref(tin[t]) - 2 * f1.pref(tin[lc]);
      |                                                                 ^~
      |                                                                 lca
currencies.cpp: In function 'int main()':
currencies.cpp:179:3: error: 'lc' was not declared in this scope; did you mean 'l'?
  179 |   lc = lca(s, t);
      |   ^~
      |   l