제출 #1124659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124659		Tyx2019	Two Currencies (JOI23_currencies)	C++20	0 / 100	1472 ms	1114112 KiB

currencies

#include <bits/stdc++.h>
#define int long long 
#define debug(x) if(0) cout << #x << " is " << x << endl;
using namespace std;
	int N, M, Q;

struct node{
	int S, E, M, V, ladd;
	node *l, *r;
	//range add, point query 
	node(int _S, int _E, int _V = 0, int _ladd = 0){
		S = _S;
		E = _E;
		V = _V;
		ladd = _ladd;
		l = r = NULL;
		M = (S + E) >> 1;
	}
	node(node *other){
		S = other->S;
		E = other->E;
		V = other->V;
		ladd = other->V;
		l = other->l;
		r = other->r;
		M = other->M;
	}
	void prop(){
		if(S == E) return;
		if(!l){
			l = new node(S, M);
			r = new node(M + 1, E);
		}
		else{
			node *cpyl = new node(l);
			cpyl->S = l->S;
			cpyl->E = l->E;
			cpyl->M = l->M;
			cpyl->V = l->V;
			cpyl->ladd = l->ladd;
			cpyl->l = l->l;
			cpyl->r = l->r;
			l = cpyl;
			node *cpyr = new node(r);
			cpyr->S = r->S;
			cpyr->E = r->E;
			cpyr->M = r->M;
			cpyr->V = r->V;
			cpyr->ladd = r->ladd;
			cpyr->l = r->l;
			cpyr->r = r->r;
			r = cpyr;
		}
		if(ladd != 0){
			l->V += (M - S + 1) * ladd;
			r->V += (E - M) * ladd;
			l->ladd += ladd;
			r->ladd += ladd;
			ladd = 0;
		}
	}
	int query(int x){
		prop();
		if(S == E) return V;
		if(x <= M) return l->query(x);
		else return r->query(x);
	}
	node* upd(int start, int end, int val){
		prop();
		if(start == S && end == E){
			node *cpy = new node(S, E, V + (E - S + 1) * val, ladd + val);
			cpy->l = l;
			cpy->r = r;
			return cpy;
		}
		else if(end <= M){
			node* cpyl = l->upd(start, end, val);
			node* cpy = new node(S, E, cpyl->V + r->V, ladd);
			cpy->l = cpyl;
			cpy->r = r;
			return cpy;
		}
		else if(start > M){
			node* cpyr = r->upd(start, end, val);
			node* cpy = new node(S, E, cpyr->V + l->V, ladd);
			cpy->l = l;
			cpy->r = cpyr;
			return cpy;
		}
		else{
			node* cpyl = l->upd(start, M, val);
			node* cpyr = r->upd(M + 1, end, val);
			node* cpy = new node(S, E, cpyl->V + cpyr->V, ladd);
			cpy->l = cpyl;
			cpy->r = cpyr;
			return cpy;
		}
	}
}*seggssum, *seggscnt;
const int maxN = 1e5 + 5;
vector<int> adj[maxN];
int order[maxN];
int cur = 0;
int mem[maxN][20];
int depth[maxN];
int streesz[maxN];
void dfs(int x, int par){
	order[x] = cur++;
	mem[x][0] = par;
	streesz[x] = 1;
	for(auto j:adj[x]){
		if(j == par) continue;
		depth[j] = depth[x] + 1;
		dfs(j, x);
		streesz[x] += streesz[j];
	}
}
int anc(int x, int k){
	int cur = x;
	for(int i=19;i>=0;i--){
		if(((1 << i) & k) != 0){
			cur = mem[cur][i];
		}
	}
	return cur;
}
int lcaa(int x, int y){
	if(depth[x] < depth[y]) swap(x, y);
	int k = depth[x] - depth[y];
	x = anc(x, k);
	assert(min(x, y) != -1);
	assert(k >= 0);
	if(x == y) return x;
	for(int i=19;i>=0;i--){
		if(mem[x][i] != mem[y][i]){
			x = mem[x][i];
			y = mem[y][i];
		}
	}
	
	return mem[x][0];
}
main(){
	cin >> N >> M >> Q;
	seggssum = new node(0, N + 5);
	seggscnt = new node(0, N + 5);
	int A[N], B[N];
	for(int i=1;i<=N-1;i++) cin >> A[i] >> B[i];
	for(int i=1;i<=N-1;i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	depth[1] = 0;
	dfs(1, -1);
	//2k
	for(int i=1;i<=N;i++){
		for(int j=1;j<20;j++){
			int hpar = mem[i][j-1];
			if(hpar == -1) mem[i][j] = -1;
			else mem[i][j] = mem[hpar][j-1];
		}
	}
	int C[M], P[M];
	for(int i=0;i<M;i++){
		cin >> P[i] >> C[i];
	}
	int S[Q], T[Q], X[Q], Y[Q], lca[Q];
	for(int i=0;i<Q;i++){
		cin >> S[i] >> T[i] >> X[i] >> Y[i];
		lca[i] = lcaa(S[i], T[i]);
	}
	vector<pair<int, int>> V;
	for(int i=0;i<M;i++){
		V.push_back({C[i], P[i]});
	}
	sort(V.begin(), V.end());
	node* sum[M + 5];
	node* count[M + 5];
	sum[0] = seggssum;
	count[0] = seggscnt;
	for(int i=1;i<=M;i++){
		int x = V[i-1].second;
		int bruh = A[x];
		if(depth[B[x]] >= depth[bruh]) bruh = B[x];
		sum[i] = sum[i-1]->upd(order[bruh], order[bruh] + streesz[bruh] - 1, V[i-1].first);
		count[i] = count[i-1]->upd(order[bruh], order[bruh] + streesz[bruh] - 1, 1);
	}
	debug("hi");
	for(int i=0;i<Q;i++){
		int lb = 0;
		int ub = M;
		while(ub > lb){
			int m = (ub + lb + 1) >> 1;
			int s = sum[m]->query(order[S[i]]);
			int t = sum[m]->query(order[T[i]]);
			int l = sum[m]->query(order[lca[i]]);
			if((s + t - (2 * l)) <= Y[i]) lb = m;
			else ub = m - 1;
		}
		debug(sum[2]->query(order[S[i]]));
		debug(sum[2]->query(order[T[i]]));
		debug(sum[2]->query(order[lca[i]]));
		int s = count[lb]->query(order[S[i]]);
		int t = count[lb]->query(order[T[i]]);
		int l = count[lb]->query(order[lca[i]]);
		int k = s + t - (2 * l);
		debug(s);
		debug(t);
		debug(l);
		debug(lca[i]);
		s = count[M]->query(order[S[i]]);
		t = count[M]->query(order[T[i]]);
		l = count[M]->query(order[lca[i]]);
		debug(lb);
		int tot = s + t - (2 * l);
		debug(tot);
		int nec = tot - k;
		int res = X[i] - nec;
		if(res < 0){
			cout << "-1\n";
		}
		else cout << res << '\n';
	}
	for(int i=1;i<=N;i++) debug(order[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp:143:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  143 | main(){
      | ^~~~

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