Submission #735215

#	Time	Username	Problem	Language	Result	Execution time	Memory
735215		arnold518	Two Currencies (JOI23_currencies)	C++17	100 / 100	1620 ms	41416 KiB

currencies

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, Q;
vector<pii> adj[MAXN+10];
pii A[MAXN+10];

struct SEG
{
	ll tree[MAXN*4+10];
	void init()
	{
		fill(tree, tree+MAXN*4+10, 0);
	}
	void update(int node, int tl, int tr, int l, int r, ll k)
	{
		if(l<=tl && tr<=r)
		{
			tree[node]+=k;
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	ll query(int node, int tl, int tr, int k)
	{
		if(tl==tr) return tree[node];
		int mid=tl+tr>>1;
		if(k<=mid) return tree[node]+query(node*2, tl, mid ,k);
		else return tree[node]+query(node*2+1, mid+1, tr, k);
	}
}seg;

int L[MAXN+10], R[MAXN+10], dep[MAXN+10], par[MAXN+10][30], cnt, P[MAXN+10];
void dfs(int now, int bef, int d)
{
	L[now]=++cnt;
	par[now][0]=bef;
	dep[now]=d;
	for(auto [nxt, e] : adj[now])
	{
		if(nxt==bef) continue;
		P[e]=nxt;
		dfs(nxt, now, d+1);
	}
	R[now]=cnt;
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

int C[MAXN+10];
pii B[MAXN+10];
pll D[MAXN+10];
int lo[MAXN+10], hi[MAXN+10];
int E[MAXN+10];

ll f(int p)
{
	int u=B[p].first, v=B[p].second, w=C[p];
	return seg.query(1, 1, N, L[u])+seg.query(1, 1, N, L[v])-2*seg.query(1, 1, N, L[w]);
}

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	for(int i=1; i<=M; i++) scanf("%d%d", &A[i].second, &A[i].first);

	dfs(1, 1, 1);
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(int i=1; i<=Q; i++) scanf("%d%d%lld%lld", &B[i].first, &B[i].second, &D[i].first, &D[i].second), C[i]=lca(B[i].first, B[i].second);

	sort(A+1, A+M+1);

	for(int i=1; i<=Q; i++) lo[i]=0, hi[i]=M+1;
	while(1)
	{
		vector<pii> V;
		for(int i=1; i<=Q; i++)
		{
			if(lo[i]+1<hi[i])
			{
				V.push_back({lo[i]+hi[i]>>1, i});
			}
		}
		if(V.empty()) break;
		sort(V.begin(), V.end());

		seg.init();
		int pt=1;
		for(auto it : V)
		{
			for(; pt<=M && pt<=it.first; pt++)
			{
				seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], A[pt].first);
			}
			//printf("??%d %d %lld %d\n", it.first, it.second, f(it.second), D[it.second].second);
			if(f(it.second)>D[it.second].second) hi[it.second]=it.first;
			else lo[it.second]=it.first; 
		}
	}

	seg.init();
	int pt=1;
	vector<pii> V;
	for(int i=1; i<=Q; i++) V.push_back({lo[i], i});
	sort(V.begin(), V.end());
	for(auto it : V)
	{
		for(; pt<=M && pt<=it.first; pt++)
		{
			seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], 1);
		}
		E[it.second]=f(it.second);
	}
	for(; pt<=M; pt++) seg.update(1, 1, N, L[P[A[pt].second]], R[P[A[pt].second]], 1);

	for(int i=1; i<=Q; i++)
	{
		//printf("%d %d %d\n", lo[i], f(i), E[i]);
		printf("%lld\n", max(-1ll, D[i].first-f(i)+E[i]));
	}
}

Compilation message (stderr)

currencies.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
currencies.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid=tl+tr>>1;
      |           ~~^~~
currencies.cpp: In member function 'll SEG::query(int, int, int, int)':
currencies.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid=tl+tr>>1;
      |           ~~^~~
currencies.cpp: In function 'int main()':
currencies.cpp:105:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     V.push_back({lo[i]+hi[i]>>1, i});
      |                  ~~~~~^~~~~~
currencies.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
currencies.cpp:88:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  for(int i=1; i<=M; i++) scanf("%d%d", &A[i].second, &A[i].first);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:93:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  for(int i=1; i<=Q; i++) scanf("%d%d%lld%lld", &B[i].first, &B[i].second, &D[i].first, &D[i].second), C[i]=lca(B[i].first, B[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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