제출 #1263481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263481		inkvizytor	Two Currencies (JOI23_currencies)	C++20	100 / 100	1231 ms	70988 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long

const int N = 1e5 + 25, L = 30;

int lowbit(int x){
	return x & -x;
}

ll A[N], B[N], B2[N], n;

void upd(ll x, ll v, ll sus) {
    for(ll i = x ; i <= n ; i += lowbit(i)){
    	B[i] += v;
    	B2[i] += sus;
    }
}

pair<long, long> query(ll x) {
    pair<long, long> ans = {0, 0};
    for(ll i = x ; i > 0 ; i -= lowbit(i)){
    	ans.fi += B[i];
    	ans.se += B2[i];
    }
    return ans;
}

void update(ll l, ll r, ll v) {
    upd(r + 1, -v, -1); upd(l, v, 1);
}

void init() {
    fill(B, B + n + 1, 0);
    fill(B2, B2 + n + 1, 0);
}

pair<int, int> edge[N];
vector<int> e[N];

int tin[N], tout[N], timer = 0;

void dfs(int u, int par){
	tin[u] = ++timer;
	for(int v : e[u]){
		if(v == par) continue;
		dfs(v, u);
	}
	tout[u] = timer;
}

 
int par[N][L], dep[N];
 
void dfs2(int u, int p){
    dep[u] = dep[p] + 1;
    par[u][0] = p;
    for(int i = 1; i < L; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for(int v : e[u]){
        if(v == p) continue;
        dfs2(v, u);
    }
}

int gold[N];

void dfsgold(int u, int par){
	for(int v : e[u]){
		if(v == par) continue;
		gold[v] += gold[u];
		dfsgold(v, u);
	}
}
 
int ancestork(int u, int dist){
    for(int i = 0; i < L; i++){
        if(dist >> i & 1) u = par[u][i];
    }
    return u;
}
 
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    u = ancestork(u, dep[u] - dep[v]);
    if(u == v) return u;
    for(int i = L - 1; i >= 0; i--){
        if(par[v][i] != par[u][i]){
            v = par[v][i];
            u = par[u][i];
        }
    }
    int l = par[v][0];
    return l;
}

pair<long, long> distroot(ll x){
	return query(tin[x]);
}

pair<long, long> path(int u, int v){
	pair<long, long> res = {0, 0};
	pair<long, long> p1 = distroot(u), p2 = distroot(v), p3 = distroot(lca(u, v));
	res.fi = p1.fi + p2.fi - p3.fi * 2;
	res.se = p1.se + p2.se - p3.se * 2;
	return res;
}


int goldpath(int u, int v){
	return gold[u] + gold[v] - gold[lca(u, v)] * 2;
}

pair<long, long> p[N];

int s[N], t[N]; ll x[N], y[N];

struct bs{
	int l, r, mid, id;
};

bs b[N];
int sus[N];

vector<bs> midcur[N];

void solve(){
	int m, q;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
		edge[i] = {u, v};
	}

	for(int i = 1; i <= m; i++){
		cin >> p[i].se >> p[i].fi;
	}
	sort(p + 1, p + m + 1);

	dfs(1, -1);
	dfs2(1, -1);

	for(int i = 1; i < n; i++){
		int u = edge[i].fi, v = edge[i].se;
		if(tin[u] > tin[v]) swap(edge[i].fi, edge[i].se);
	}

	for(int i = 1; i <= m; i++){
		gold[edge[p[i].se].se]++;
	}

	dfsgold(1, -1);

	for(int i = 1; i <= q; i++){
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		b[i] = {0, m, 1, i};
	}

	for(int z = 1; z < L; z++){
		init();
		for(int i = 0; i <= m; i++){
			midcur[i].clear();
		}
		for(int i = 1; i <= q; i++){
			b[i].mid = (b[i].l + b[i].r + 1) / 2;
			midcur[b[i].mid].push_back(b[i]);
		}
		for(int i = 1; i <= m; i++){
			int id = p[i].se;
			int u = edge[id].fi, v = edge[id].se;
			update(tin[v], tout[v], p[i].fi);
			for(auto [l, r, mid, id] : midcur[i]){
				if(l == r) continue;
				u = s[id], v = t[id];
				pair<long, long> cur = path(u, v);
				if(cur.fi <= y[id]){
					b[id].l = mid;
					sus[id] = cur.se;
				}else{
					b[id].r = mid - 1;
				}
			}
		}
	}

	for(int i = 1; i <= q; i++){
		int g = goldpath(s[i], t[i]);
		int silver_used = sus[i];
		int gold_used = g - silver_used;
		if(gold_used > x[i]){
			cout << -1 << '\n';
		}else{
			cout << x[i] - gold_used << '\n';
		}
	}
}


int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	int m, q;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
		edge[i] = {u, v};
	}

	for(int i = 1; i <= m; i++){
		cin >> p[i].se >> p[i].fi;
	}
	sort(p + 1, p + m + 1);

	dfs(1, -1);
	dfs2(1, -1);

	for(int i = 1; i < n; i++){
		int u = edge[i].fi, v = edge[i].se;
		if(tin[u] > tin[v]) swap(edge[i].fi, edge[i].se);
	}

	for(int i = 1; i <= m; i++){
		gold[edge[p[i].se].se]++;
	}

	dfsgold(1, -1);

	for(int i = 1; i <= q; i++){
		cin >> s[i] >> t[i] >> x[i] >> y[i];
		b[i] = {0, m, 1, i};
	}

	for(int z = 1; z < L; z++){
		init();
		for(int i = 0; i <= m; i++){
			midcur[i].clear();
		}
		for(int i = 1; i <= q; i++){
			b[i].mid = (b[i].l + b[i].r + 1) / 2;
			midcur[b[i].mid].push_back(b[i]);
		}
		for(int i = 1; i <= m; i++){
			int id = p[i].se;
			int u = edge[id].fi, v = edge[id].se;
			update(tin[v], tout[v], p[i].fi);
			for(auto [l, r, mid, id] : midcur[i]){
				if(l == r) continue;
				u = s[id], v = t[id];
				pair<long, long> cur = path(u, v);
				if(cur.fi <= y[id]){
					b[id].l = mid;
					sus[id] = cur.se;
				}else{
					b[id].r = mid - 1;
				}
			}
		}
	}

	for(int i = 1; i <= q; i++){
		int g = goldpath(s[i], t[i]);
		int silver_used = sus[i];
		int gold_used = g - silver_used;
		if(gold_used > x[i]){
			cout << -1 << '\n';
		}else{
			cout << x[i] - gold_used << '\n';
		}
	}
}

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