Submission #1184937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184937		SmuggingSpun	Two Currencies (JOI23_currencies)	C++20	10 / 100	62 ms	10820 KiB

currencies

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int lim = 1e5 + 5;
int n, m, q, u[lim], v[lim];
vector<int>g[lim], c[lim];
namespace sub1{
	void solve(){
		queue<int>Q;
		vector<int>h(n + 1, -1), parent(n + 1);
		vector<vector<int>>value(n + 1);
		Q.push(parent[1] = h[1] = 1);
		while(!Q.empty()){
			int s = Q.front();
			Q.pop();
			for(int& i : g[s]){
				int d = u[i] ^ v[i] ^ s;
				if(h[d] == -1){
					h[d] = h[parent[d] = s] + 1;
					value[d] = c[i];
					Q.push(d);
				}
			}
		}
		for(int _ = 0; _ < q; _++){
			int s, t, x;
			ll y;
			cin >> s >> t >> x >> y;
			vector<int>path_value;
			while(s != t){
				if(h[s] < h[t]){
					swap(s, t);
				}
				for(int& x : value[s]){
					path_value.emplace_back(x);
				}
				s = parent[s];
			}
			sort(path_value.begin(), path_value.end());
			int p = path_value.size();
			for(int i = 0; i < path_value.size(); i++){
				if((y -= path_value[i]) < 0){
					p = i;
					break;
				}
			}
			cout << max(-1, x - int(path_value.size()) + p) << "\n";
		}
	}
}
namespace sub23{
	struct Node{
		int lc, rc, cnt;
		ll sum;
		Node(){
			this->lc = this->rc = -1;
			this->cnt = 0;
			this->sum = 0;
		}	
	};
	vector<Node>st;
	void solve(){
		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i];
		g[u[i]].emplace_back(i);
		g[v[i]].emplace_back(i);
	}
	memset(c, 0, sizeof(c));
	for(int i = 0; i < m; i++){
		int p, x;
		cin >> p >> x;
		c[p].emplace_back(x);
	}
	if(max(max(n, m), q) <= 2000){
		sub1::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:70:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32