Submission #1308086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308086		thuhienne	Two Currencies (JOI23_currencies)	C++20	100 / 100	272 ms	68504 KiB

currencies

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

using ll = long long;

#define thuhien ""
#define re exit(0);

const int maxn = 100009;
const int LOG = 17;

ll fen[maxn];
int fencnt[maxn];
void update(int pos,int val) {
	for (;pos <= 100003;pos += (pos & -pos)) {
		fen[pos] += val;
		fencnt[pos] += val < 0 ? -1 : 1;
	}
}
void update(int l,int r,int val) {
	update(l,val);
	update(r + 1,-val);
}
ll get(int pos) {
	ll ret = 0;
	for (;pos;pos -= (pos & -pos)) ret += fen[pos];
	return ret;
}
int getnum(int pos) {
	int ret = 0;
	for (;pos;pos -= (pos & -pos)) ret += fencnt[pos];
	return ret;
}

int n,m,q;
vector <int> adj[maxn];
pair <int,int> edge[maxn];

pair <int,int> checkpoints[maxn];

int tin[maxn],tout[maxn],timedfs;
int h[maxn],up[maxn][LOG + 1],depth[maxn];

void predfs(int node,int par) {
	tin[node] = ++timedfs;
	for (int x : adj[node]) if (x != par) {
		h[x] = h[node] + 1;
		up[x][0] = node;
		for (int i = 1;i <= LOG;i++) {
			up[x][i] = up[up[x][i - 1]][i - 1];
		}
		predfs(x,node);
	}
	tout[node] = timedfs;
}
void dfs(int node,int par) {
	for (int x : adj[node]) if (x != par) {
		depth[x] += depth[node];
		dfs(x,node);
	}
}
int lca(int u,int v) {
	if (h[u] < h[v]) swap(u,v);
	int diff = h[u] - h[v];
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) u = up[u][i];
	if (u == v) return u;
	for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
		u = up[u][i];
		v = up[v][i];
	}
	return up[u][0];
}

struct ped {
	int u,v,lca,gold;
	ll silver;
	int index;
};

int answer[maxn];

int pt = 0;

void move(int mid) {
	while (pt < mid) {
		pt++;
		int u = checkpoints[pt].first;
		update(tin[u],tout[u],checkpoints[pt].second);
	}
	while (pt > mid) {
		int u = checkpoints[pt].first;
		update(tin[u],tout[u],-checkpoints[pt].second);
		pt--;
	}
}

void binsearch(int l,int r,vector <ped> all) {
	if (l > r) {
		move(r);
		for (ped x : all) {
			int temp = getnum(tin[x.u]) + getnum(tin[x.v]) - 2*getnum(tin[x.lca]);
			int temp2 = depth[x.u] + depth[x.v] - 2*depth[x.lca];
			answer[x.index] = max(-1,x.gold - (temp2 - temp));
//			answer[x.index] = r;
		}
		return;
	}
	if (all.empty()) return;
	
	int mid = (l + r) >> 1;
	
	move(mid);
	
	vector <ped> left,right;
	for (ped x : all) {
		ll DICK = get(tin[x.u]) + get(tin[x.v]) - 2*get(tin[x.lca]);
//		if (x.u == 5 && x.v == 3) cout << DICK << " " << l << " " << r << " " << x.silver << '\n';
		if (DICK <= x.silver) right.push_back(x); //l = mid + 1;
		else left.push_back(x); //r = mid - 1;
	}
	
	binsearch(l,mid - 1,left);
	left.clear();
	binsearch(mid + 1,r,right);
	right.clear();
	
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}

	cin >> n >> m >> q;
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edge[i] = {u,v};
	}
	
	predfs(1,-1);
	
	for (int i = 1;i <= m;i++) {
		int a;
		cin >> a >> checkpoints[i].second;
		
		int u = edge[a].first,v = edge[a].second;
		if (h[u] < h[v]) swap(u,v);
		
		checkpoints[i].first = u;
		depth[u] ++;
	}
	sort(checkpoints + 1,checkpoints + 1 + m,[] (pair <int,int> a,pair <int,int> b) {
		return a.second < b.second;
	});
	
	dfs(1,-1);
	
	vector <ped> all; 
	for (int i = 1;i <= q;i++) {
		int u,v,gold;ll silver;cin >> u >> v >> gold >> silver;
		all.push_back({u,v,lca(u,v),gold,silver,i});
	}
	
	binsearch(1,m,all);
	
	for (int i = 1;i <= q;i++) cout << answer[i] << '\n';

}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:133:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:134:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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