oj.uz

답안 #917803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917803 2024-01-28T19:44:48 Z denniskim Two Currencies (JOI23_currencies) C++17
100 / 100
 2557 ms 49628 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll S, T, X, Y;
};

ll n, m, q;
ll all, bll;
pll edg[100010];
pll cost[100010];
vector<ll> vec[100010];
gujo qry[100010];
ll l[100010], r[100010], mid[100010];
ll IN[100010], OUT[100010], cc;
ll spa[100010][21], dep[100010];
ll ans[100010];

struct fenwicktree
{
	ll bit[100010];
	
	void init(void)
	{
		for(ll i = 1 ; i <= n ; i++)
			bit[i] = 0;
	}
	
	void update(ll w, ll v)
	{
		for(ll i = w ; i <= n ; i += (i & (-i)))
			bit[i] += v;
	}
	
	ll query(ll w)
	{
		ll ret = 0;
		
		for(ll i = w ; i >= 1 ; i -= (i & (-i)))
			ret += bit[i];
		
		return ret;
	}
}BIT;

void dfs0(ll here, ll pa)
{
	IN[here] = ++cc;
	spa[here][0] = pa;
	dep[here] = dep[pa] + 1;
	
	for(auto &i : vec[here])
	{
		if(i == pa)
			continue;
		
		dfs0(i, here);
	}
	
	OUT[here] = cc;
}

ll LCA(ll X, ll Y)
{
	if(dep[X] < dep[Y])
		swap(X, Y);
	
	ll cha = dep[X] - dep[Y];
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(cha >= (1LL << i))
		{
			cha -= (1LL << i);
			X = spa[X][i];
		}
	}
	
	if(X == Y)
		return X;
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(spa[X][i] != spa[Y][i])
		{
			X = spa[X][i];
			Y = spa[Y][i];
		}
	}
	
	return spa[X][0];
}

int main(void)
{
	fastio
	
	cin >> n >> m >> q;
	
	for(ll i = 1 ; i < n ; i++)
	{
		cin >> all >> bll;
		
		edg[i] = {all, bll};
		vec[all].push_back(bll);
		vec[bll].push_back(all);
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		cin >> all >> bll;
		cost[i] = {bll, all};
	}
	
	sort(cost + 1, cost + 1 + m);
	
	for(ll i = 1 ; i <= q ; i++)
		cin >> qry[i].S >> qry[i].T >> qry[i].X >> qry[i].Y;
	
	dfs0(1, 0);
	
	for(ll i = 1 ; i < n ; i++)
	{
		if(dep[edg[i].fi] < dep[edg[i].se])
			swap(edg[i].fi, edg[i].se);
	}
	
	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
			spa[j][i] = spa[spa[j][i - 1]][i - 1];
	}
	
	for(ll i = 1 ; i <= q ; i++)
		l[i] = 1, r[i] = m;
	
	for(ll o = 0 ; o <= 20 ; o++)
	{
		vector<pll> Q;
		
		for(ll i = 1 ; i <= q ; i++)
		{
			mid[i] = (l[i] + r[i]) >> 1;
			
			if(l[i] <= r[i])
				Q.push_back({mid[i], i});
		}
		
		if(Q.empty())
			break;
		
		BIT.init();
		sort(Q.begin(), Q.end());
		
		ll p = 0;
		
		for(ll i = 1 ; i <= m ; i++)
		{
			pll V = edg[cost[i].se];
			
			BIT.update(IN[V.fi], cost[i].fi);
			BIT.update(OUT[V.fi] + 1, -cost[i].fi);
			
			while(p < (ll)Q.size() && Q[p].fi <= i)
			{
				ll num = Q[p].se;
				ll gap = 0;
				
				gap = BIT.query(IN[qry[num].S]) + BIT.query(IN[qry[num].T]) - 2 * BIT.query(IN[LCA(qry[num].S, qry[num].T)]);
				
				if(gap > qry[num].Y)
					r[num] = mid[num] - 1;
				else
					l[num] = mid[num] + 1;
				
				p++;
			}
		}
	}
	
	vector<pll> Q;
	
	for(ll i = 1 ; i <= q ; i++)
		Q.push_back({r[i], i});
	
	sort(Q.begin(), Q.end());
	BIT.init();
	
	ll p = 0;
	
	while(p < (ll)Q.size() && Q[p].fi <= 0)
	{
		ll num = Q[p].se;
		ll gap = 0;
		
		ans[num] -= BIT.query(IN[qry[num].S]) + BIT.query(IN[qry[num].T]) - 2 * BIT.query(IN[LCA(qry[num].S, qry[num].T)]);
		p++;
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		pll V = edg[cost[i].se];
		
		BIT.update(IN[V.fi], 1);
		BIT.update(OUT[V.fi] + 1, -1);
		
		while(p < (ll)Q.size() && Q[p].fi <= i)
		{
			ll num = Q[p].se;
			ll gap = 0;
			
			ans[num] -= BIT.query(IN[qry[num].S]) + BIT.query(IN[qry[num].T]) - 2 * BIT.query(IN[LCA(qry[num].S, qry[num].T)]);
			p++;
		}
	}
	
	for(ll i = 1 ; i <= q ; i++)
		ans[i] += BIT.query(IN[qry[i].S]) + BIT.query(IN[qry[i].T]) - 2 * BIT.query(IN[LCA(qry[i].S, qry[i].T)]);
	
	for(ll i = 1 ; i <= q ; i++)
	{
		if(ans[i] > qry[i].X)
			cout << -1 en;
		else
			cout << qry[i].X - ans[i] en;
	}
	
	return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:210:6: warning: unused variable 'gap' [-Wunused-variable]
  210 |   ll gap = 0;
      |      ^~~
currencies.cpp:226:7: warning: unused variable 'gap' [-Wunused-variable]
  226 |    ll gap = 0;
      |       ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 7 ms 10844 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 10 ms 12892 KB Output is correct
8 Correct 11 ms 13128 KB Output is correct
9 Correct 10 ms 12892 KB Output is correct
10 Correct 11 ms 13404 KB Output is correct
11 Correct 10 ms 12892 KB Output is correct
12 Correct 11 ms 12892 KB Output is correct
13 Correct 9 ms 13148 KB Output is correct
14 Correct 10 ms 13152 KB Output is correct
15 Correct 11 ms 13148 KB Output is correct
16 Correct 10 ms 13148 KB Output is correct
17 Correct 11 ms 12892 KB Output is correct
18 Correct 10 ms 12924 KB Output is correct
19 Correct 10 ms 12892 KB Output is correct
20 Correct 11 ms 13116 KB Output is correct
21 Correct 9 ms 12892 KB Output is correct
22 Correct 9 ms 12928 KB Output is correct
23 Correct 10 ms 12888 KB Output is correct
24 Correct 9 ms 13116 KB Output is correct
25 Correct 10 ms 12892 KB Output is correct
26 Correct 9 ms 12892 KB Output is correct
27 Correct 9 ms 12888 KB Output is correct
28 Correct 9 ms 13020 KB Output is correct
29 Correct 9 ms 12892 KB Output is correct
30 Correct 10 ms 12892 KB Output is correct
31 Correct 10 ms 12892 KB Output is correct
32 Correct 10 ms 12892 KB Output is correct
33 Correct 8 ms 13148 KB Output is correct
34 Correct 9 ms 13388 KB Output is correct
35 Correct 9 ms 13148 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 10 ms 13100 KB Output is correct
3 Correct 10 ms 13100 KB Output is correct
4 Correct 11 ms 12892 KB Output is correct
5 Correct 797 ms 41708 KB Output is correct
6 Correct 1000 ms 37844 KB Output is correct
7 Correct 1059 ms 40408 KB Output is correct
8 Correct 747 ms 39304 KB Output is correct
9 Correct 703 ms 38028 KB Output is correct
10 Correct 1480 ms 44476 KB Output is correct
11 Correct 1378 ms 44608 KB Output is correct
12 Correct 1485 ms 44804 KB Output is correct
13 Correct 1411 ms 44600 KB Output is correct
14 Correct 1371 ms 44624 KB Output is correct
15 Correct 2086 ms 49028 KB Output is correct
16 Correct 2557 ms 49220 KB Output is correct
17 Correct 2318 ms 48580 KB Output is correct
18 Correct 2085 ms 44336 KB Output is correct
19 Correct 1951 ms 44324 KB Output is correct
20 Correct 1810 ms 44344 KB Output is correct
21 Correct 1166 ms 43844 KB Output is correct
22 Correct 1222 ms 44192 KB Output is correct
23 Correct 1160 ms 44244 KB Output is correct
24 Correct 1159 ms 44264 KB Output is correct
25 Correct 1037 ms 45204 KB Output is correct
26 Correct 1032 ms 44960 KB Output is correct
27 Correct 984 ms 45004 KB Output is correct
28 Correct 589 ms 44364 KB Output is correct
29 Correct 564 ms 44260 KB Output is correct
30 Correct 697 ms 44424 KB Output is correct
31 Correct 698 ms 44648 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 8 ms 13148 KB Output is correct
3 Correct 9 ms 13144 KB Output is correct
4 Correct 9 ms 13144 KB Output is correct
5 Correct 1280 ms 45200 KB Output is correct
6 Correct 1188 ms 46072 KB Output is correct
7 Correct 822 ms 36956 KB Output is correct
8 Correct 2053 ms 49628 KB Output is correct
9 Correct 2158 ms 49520 KB Output is correct
10 Correct 2552 ms 49276 KB Output is correct
11 Correct 1052 ms 49212 KB Output is correct
12 Correct 1165 ms 49216 KB Output is correct
13 Correct 1080 ms 49296 KB Output is correct
14 Correct 496 ms 49124 KB Output is correct
15 Correct 500 ms 49140 KB Output is correct
16 Correct 838 ms 49372 KB Output is correct
17 Correct 789 ms 49412 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 7 ms 10844 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 10 ms 12892 KB Output is correct
8 Correct 11 ms 13128 KB Output is correct
9 Correct 10 ms 12892 KB Output is correct
10 Correct 11 ms 13404 KB Output is correct
11 Correct 10 ms 12892 KB Output is correct
12 Correct 11 ms 12892 KB Output is correct
13 Correct 9 ms 13148 KB Output is correct
14 Correct 10 ms 13152 KB Output is correct
15 Correct 11 ms 13148 KB Output is correct
16 Correct 10 ms 13148 KB Output is correct
17 Correct 11 ms 12892 KB Output is correct
18 Correct 10 ms 12924 KB Output is correct
19 Correct 10 ms 12892 KB Output is correct
20 Correct 11 ms 13116 KB Output is correct
21 Correct 9 ms 12892 KB Output is correct
22 Correct 9 ms 12928 KB Output is correct
23 Correct 10 ms 12888 KB Output is correct
24 Correct 9 ms 13116 KB Output is correct
25 Correct 10 ms 12892 KB Output is correct
26 Correct 9 ms 12892 KB Output is correct
27 Correct 9 ms 12888 KB Output is correct
28 Correct 9 ms 13020 KB Output is correct
29 Correct 9 ms 12892 KB Output is correct
30 Correct 10 ms 12892 KB Output is correct
31 Correct 10 ms 12892 KB Output is correct
32 Correct 10 ms 12892 KB Output is correct
33 Correct 8 ms 13148 KB Output is correct
34 Correct 9 ms 13388 KB Output is correct
35 Correct 9 ms 13148 KB Output is correct
36 Correct 2 ms 10588 KB Output is correct
37 Correct 10 ms 13100 KB Output is correct
38 Correct 10 ms 13100 KB Output is correct
39 Correct 11 ms 12892 KB Output is correct
40 Correct 797 ms 41708 KB Output is correct
41 Correct 1000 ms 37844 KB Output is correct
42 Correct 1059 ms 40408 KB Output is correct
43 Correct 747 ms 39304 KB Output is correct
44 Correct 703 ms 38028 KB Output is correct
45 Correct 1480 ms 44476 KB Output is correct
46 Correct 1378 ms 44608 KB Output is correct
47 Correct 1485 ms 44804 KB Output is correct
48 Correct 1411 ms 44600 KB Output is correct
49 Correct 1371 ms 44624 KB Output is correct
50 Correct 2086 ms 49028 KB Output is correct
51 Correct 2557 ms 49220 KB Output is correct
52 Correct 2318 ms 48580 KB Output is correct
53 Correct 2085 ms 44336 KB Output is correct
54 Correct 1951 ms 44324 KB Output is correct
55 Correct 1810 ms 44344 KB Output is correct
56 Correct 1166 ms 43844 KB Output is correct
57 Correct 1222 ms 44192 KB Output is correct
58 Correct 1160 ms 44244 KB Output is correct
59 Correct 1159 ms 44264 KB Output is correct
60 Correct 1037 ms 45204 KB Output is correct
61 Correct 1032 ms 44960 KB Output is correct
62 Correct 984 ms 45004 KB Output is correct
63 Correct 589 ms 44364 KB Output is correct
64 Correct 564 ms 44260 KB Output is correct
65 Correct 697 ms 44424 KB Output is correct
66 Correct 698 ms 44648 KB Output is correct
67 Correct 2 ms 10584 KB Output is correct
68 Correct 8 ms 13148 KB Output is correct
69 Correct 9 ms 13144 KB Output is correct
70 Correct 9 ms 13144 KB Output is correct
71 Correct 1280 ms 45200 KB Output is correct
72 Correct 1188 ms 46072 KB Output is correct
73 Correct 822 ms 36956 KB Output is correct
74 Correct 2053 ms 49628 KB Output is correct
75 Correct 2158 ms 49520 KB Output is correct
76 Correct 2552 ms 49276 KB Output is correct
77 Correct 1052 ms 49212 KB Output is correct
78 Correct 1165 ms 49216 KB Output is correct
79 Correct 1080 ms 49296 KB Output is correct
80 Correct 496 ms 49124 KB Output is correct
81 Correct 500 ms 49140 KB Output is correct
82 Correct 838 ms 49372 KB Output is correct
83 Correct 789 ms 49412 KB Output is correct
84 Correct 971 ms 38292 KB Output is correct
85 Correct 968 ms 33292 KB Output is correct
86 Correct 1061 ms 32916 KB Output is correct
87 Correct 1953 ms 44436 KB Output is correct
88 Correct 1761 ms 44364 KB Output is correct
89 Correct 1679 ms 44320 KB Output is correct
90 Correct 1688 ms 44472 KB Output is correct
91 Correct 1714 ms 44468 KB Output is correct
92 Correct 2436 ms 47468 KB Output is correct
93 Correct 2267 ms 48412 KB Output is correct
94 Correct 2150 ms 44980 KB Output is correct
95 Correct 2212 ms 44248 KB Output is correct
96 Correct 2196 ms 44432 KB Output is correct
97 Correct 2164 ms 44576 KB Output is correct
98 Correct 1363 ms 44224 KB Output is correct
99 Correct 1338 ms 44388 KB Output is correct
100 Correct 1351 ms 44264 KB Output is correct
101 Correct 1367 ms 44248 KB Output is correct
102 Correct 1141 ms 44808 KB Output is correct
103 Correct 1129 ms 45096 KB Output is correct
104 Correct 1407 ms 44764 KB Output is correct
105 Correct 911 ms 44480 KB Output is correct
106 Correct 899 ms 44384 KB Output is correct
107 Correct 1097 ms 44272 KB Output is correct
108 Correct 903 ms 44504 KB Output is correct