oj.uz

답안 #769383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769383 2023-06-29T13:39:04 Z Arturgo Two Currencies (JOI23_currencies) C++14
100 / 100
 4859 ms 42500 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> prixs[100 * 1000 + 42];
vector<pair<int, int>> voisins[100 * 1000 + 42];

vector<tuple<int, int, int>> index_to_val;

int posSommet[100 * 1000 + 42];
vector<int> events;

void dfs(int u, int parent = -1) {
	posSommet[u] = events.size();
	
	for(pair<int, int> edge : voisins[u]) {
		if(edge.first == parent) continue;
		
		for(int prix : prixs[edge.second])
			events.push_back(prix);
		
		dfs(edge.first, u);
		
		for(int prix : prixs[edge.second])
			events.push_back(prix);
	}
}

struct Req {
	int batch;
	int id, deb, fin, gold, silver;
};

bool operator < (const Req& a, const Req& b) {
	if(a.batch != b.batch) return a.batch < b.batch;
	if(a.fin != b.fin) return a.fin < b.fin;
	return a.deb < b.deb;
}

int sommeSous[(1 << 20)];
int nbSous[(1 << 20)];

void ajoute(int pos, int val) {
	pos += (1 << 19);
	
	while(pos != 0) {
		sommeSous[pos] += val;
		nbSous[pos] += (val > 0)?1:-1;
		pos /= 2;
	}
}

int gold_keep(int pos, int val) {
	if(pos >= (1 << 19)) {
		return 0;
	}
	
	if(sommeSous[2 * pos] <= val) 
		return gold_keep(2 * pos + 1, val - sommeSous[2 * pos]) + nbSous[2 * pos];
	return gold_keep(2 * pos, val);
}

bool presents[100 * 1000 + 42];

void swp(int prix) {
	if(!presents[prix]) {
		ajoute(prix, get<0>(index_to_val[prix]));
	}
	else {
		ajoute(prix, -get<0>(index_to_val[prix]));
	}
	presents[prix] = !presents[prix];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int nbSommets, nbChecks, nbReqs;
	cin >> nbSommets >> nbChecks >> nbReqs;
	
	for(int iRoute = 0;iRoute < nbSommets - 1;iRoute++) {
		int deb, fin;
		cin >> deb >> fin;
		deb--; fin--;
		voisins[deb].push_back({fin, iRoute});
		voisins[fin].push_back({deb, iRoute});
	}
	
	for(int iCheck = 0;iCheck < nbChecks;iCheck++) {
		int route, prix;
		cin >> route >> prix;
		route--;
		index_to_val.push_back({prix, route, prixs[route].size()});
		prixs[route].push_back(prix);
	}
	
	// Réindexation
	
	index_to_val.push_back({0, -1, -1});
	sort(index_to_val.begin(), index_to_val.end());
	
	for(int iTuple = 1;iTuple < (int)index_to_val.size();iTuple++) {
		tuple<int, int, int> t = index_to_val[iTuple];
		prixs[get<1>(t)][get<2>(t)] = iTuple;
	}
	
	// Mo sur arbre
	dfs(0);
	
	const int SQR = sqrt(events.size());
	
	vector<Req> reqs;
	for(int iReq = 0;iReq < nbReqs;iReq++) {
		int deb, fin, gold, silver;
		cin >> deb >> fin >> gold >> silver;
		deb--; fin--;
		
		deb = posSommet[deb];
		fin = posSommet[fin];
		if(deb > fin) swap(deb, fin);
		
		reqs.push_back({deb / SQR, iReq, deb, fin, gold, silver});
	}
	
	sort(reqs.begin(), reqs.end());
	
	vector<int> reponses(reqs.size(), -1);
	
	int d = 0, f = 0;
	for(Req r : reqs) {
		while(d < r.deb) {
			swp(events[d]);
			d++;
		}
		
		while(r.deb < d) {
			d--;
			swp(events[d]);
		}
		
		while(f < r.fin) {
			swp(events[f]);
			f++;
		}
		
		while(r.fin < f) {
			f--;
			swp(events[f]);
		}
		
		int gk = gold_keep(1, r.silver);
		
		if(nbSous[1] > r.gold + gk) reponses[r.id] = -1;
		else reponses[r.id] = r.gold + gk - nbSous[1];
	}
	
	for(int iReq = 0;iReq < nbReqs;iReq++) {
		cout << reponses[iReq] << "\n";		
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 13 ms 5612 KB Output is correct
6 Correct 14 ms 5748 KB Output is correct
7 Correct 13 ms 5692 KB Output is correct
8 Correct 15 ms 5720 KB Output is correct
9 Correct 15 ms 5688 KB Output is correct
10 Correct 15 ms 5716 KB Output is correct
11 Correct 15 ms 5716 KB Output is correct
12 Correct 15 ms 5756 KB Output is correct
13 Correct 8 ms 5844 KB Output is correct
14 Correct 10 ms 5844 KB Output is correct
15 Correct 11 ms 5828 KB Output is correct
16 Correct 12 ms 5716 KB Output is correct
17 Correct 16 ms 5716 KB Output is correct
18 Correct 12 ms 5716 KB Output is correct
19 Correct 15 ms 5680 KB Output is correct
20 Correct 15 ms 5668 KB Output is correct
21 Correct 15 ms 5736 KB Output is correct
22 Correct 15 ms 5736 KB Output is correct
23 Correct 5 ms 5716 KB Output is correct
24 Correct 7 ms 5672 KB Output is correct
25 Correct 7 ms 5684 KB Output is correct
26 Correct 5 ms 5684 KB Output is correct
27 Correct 4 ms 5716 KB Output is correct
28 Correct 9 ms 5696 KB Output is correct
29 Correct 9 ms 5704 KB Output is correct
30 Correct 14 ms 5716 KB Output is correct
31 Correct 14 ms 5756 KB Output is correct
32 Correct 15 ms 5716 KB Output is correct
33 Correct 8 ms 5844 KB Output is correct
34 Correct 9 ms 5852 KB Output is correct
35 Correct 8 ms 5844 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 14 ms 5716 KB Output is correct
3 Correct 16 ms 5760 KB Output is correct
4 Correct 17 ms 5748 KB Output is correct
5 Correct 2604 ms 27396 KB Output is correct
6 Correct 2369 ms 27296 KB Output is correct
7 Correct 1817 ms 26316 KB Output is correct
8 Correct 1599 ms 24164 KB Output is correct
9 Correct 1778 ms 24156 KB Output is correct
10 Correct 3192 ms 31248 KB Output is correct
11 Correct 3162 ms 31272 KB Output is correct
12 Correct 3211 ms 31268 KB Output is correct
13 Correct 3170 ms 31252 KB Output is correct
14 Correct 3151 ms 31240 KB Output is correct
15 Correct 2605 ms 41820 KB Output is correct
16 Correct 2822 ms 42500 KB Output is correct
17 Correct 1390 ms 41264 KB Output is correct
18 Correct 3230 ms 31668 KB Output is correct
19 Correct 3151 ms 31696 KB Output is correct
20 Correct 3197 ms 31796 KB Output is correct
21 Correct 2597 ms 30060 KB Output is correct
22 Correct 2596 ms 30248 KB Output is correct
23 Correct 2644 ms 30236 KB Output is correct
24 Correct 2595 ms 30240 KB Output is correct
25 Correct 526 ms 31220 KB Output is correct
26 Correct 402 ms 31216 KB Output is correct
27 Correct 196 ms 31088 KB Output is correct
28 Correct 114 ms 31044 KB Output is correct
29 Correct 126 ms 31084 KB Output is correct
30 Correct 2540 ms 31408 KB Output is correct
31 Correct 2553 ms 31312 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 8 ms 5844 KB Output is correct
3 Correct 8 ms 5868 KB Output is correct
4 Correct 8 ms 5860 KB Output is correct
5 Correct 816 ms 35196 KB Output is correct
6 Correct 599 ms 33860 KB Output is correct
7 Correct 1325 ms 32736 KB Output is correct
8 Correct 1465 ms 42460 KB Output is correct
9 Correct 1512 ms 42468 KB Output is correct
10 Correct 1493 ms 42460 KB Output is correct
11 Correct 403 ms 42012 KB Output is correct
12 Correct 443 ms 41960 KB Output is correct
13 Correct 463 ms 41816 KB Output is correct
14 Correct 113 ms 42280 KB Output is correct
15 Correct 120 ms 42068 KB Output is correct
16 Correct 1000 ms 42124 KB Output is correct
17 Correct 966 ms 41976 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 13 ms 5612 KB Output is correct
6 Correct 14 ms 5748 KB Output is correct
7 Correct 13 ms 5692 KB Output is correct
8 Correct 15 ms 5720 KB Output is correct
9 Correct 15 ms 5688 KB Output is correct
10 Correct 15 ms 5716 KB Output is correct
11 Correct 15 ms 5716 KB Output is correct
12 Correct 15 ms 5756 KB Output is correct
13 Correct 8 ms 5844 KB Output is correct
14 Correct 10 ms 5844 KB Output is correct
15 Correct 11 ms 5828 KB Output is correct
16 Correct 12 ms 5716 KB Output is correct
17 Correct 16 ms 5716 KB Output is correct
18 Correct 12 ms 5716 KB Output is correct
19 Correct 15 ms 5680 KB Output is correct
20 Correct 15 ms 5668 KB Output is correct
21 Correct 15 ms 5736 KB Output is correct
22 Correct 15 ms 5736 KB Output is correct
23 Correct 5 ms 5716 KB Output is correct
24 Correct 7 ms 5672 KB Output is correct
25 Correct 7 ms 5684 KB Output is correct
26 Correct 5 ms 5684 KB Output is correct
27 Correct 4 ms 5716 KB Output is correct
28 Correct 9 ms 5696 KB Output is correct
29 Correct 9 ms 5704 KB Output is correct
30 Correct 14 ms 5716 KB Output is correct
31 Correct 14 ms 5756 KB Output is correct
32 Correct 15 ms 5716 KB Output is correct
33 Correct 8 ms 5844 KB Output is correct
34 Correct 9 ms 5852 KB Output is correct
35 Correct 8 ms 5844 KB Output is correct
36 Correct 2 ms 5076 KB Output is correct
37 Correct 14 ms 5716 KB Output is correct
38 Correct 16 ms 5760 KB Output is correct
39 Correct 17 ms 5748 KB Output is correct
40 Correct 2604 ms 27396 KB Output is correct
41 Correct 2369 ms 27296 KB Output is correct
42 Correct 1817 ms 26316 KB Output is correct
43 Correct 1599 ms 24164 KB Output is correct
44 Correct 1778 ms 24156 KB Output is correct
45 Correct 3192 ms 31248 KB Output is correct
46 Correct 3162 ms 31272 KB Output is correct
47 Correct 3211 ms 31268 KB Output is correct
48 Correct 3170 ms 31252 KB Output is correct
49 Correct 3151 ms 31240 KB Output is correct
50 Correct 2605 ms 41820 KB Output is correct
51 Correct 2822 ms 42500 KB Output is correct
52 Correct 1390 ms 41264 KB Output is correct
53 Correct 3230 ms 31668 KB Output is correct
54 Correct 3151 ms 31696 KB Output is correct
55 Correct 3197 ms 31796 KB Output is correct
56 Correct 2597 ms 30060 KB Output is correct
57 Correct 2596 ms 30248 KB Output is correct
58 Correct 2644 ms 30236 KB Output is correct
59 Correct 2595 ms 30240 KB Output is correct
60 Correct 526 ms 31220 KB Output is correct
61 Correct 402 ms 31216 KB Output is correct
62 Correct 196 ms 31088 KB Output is correct
63 Correct 114 ms 31044 KB Output is correct
64 Correct 126 ms 31084 KB Output is correct
65 Correct 2540 ms 31408 KB Output is correct
66 Correct 2553 ms 31312 KB Output is correct
67 Correct 2 ms 5076 KB Output is correct
68 Correct 8 ms 5844 KB Output is correct
69 Correct 8 ms 5868 KB Output is correct
70 Correct 8 ms 5860 KB Output is correct
71 Correct 816 ms 35196 KB Output is correct
72 Correct 599 ms 33860 KB Output is correct
73 Correct 1325 ms 32736 KB Output is correct
74 Correct 1465 ms 42460 KB Output is correct
75 Correct 1512 ms 42468 KB Output is correct
76 Correct 1493 ms 42460 KB Output is correct
77 Correct 403 ms 42012 KB Output is correct
78 Correct 443 ms 41960 KB Output is correct
79 Correct 463 ms 41816 KB Output is correct
80 Correct 113 ms 42280 KB Output is correct
81 Correct 120 ms 42068 KB Output is correct
82 Correct 1000 ms 42124 KB Output is correct
83 Correct 966 ms 41976 KB Output is correct
84 Correct 2955 ms 26708 KB Output is correct
85 Correct 2558 ms 24796 KB Output is correct
86 Correct 1575 ms 22240 KB Output is correct
87 Correct 3482 ms 31072 KB Output is correct
88 Correct 3469 ms 31092 KB Output is correct
89 Correct 3508 ms 30944 KB Output is correct
90 Correct 3510 ms 30956 KB Output is correct
91 Correct 3538 ms 30904 KB Output is correct
92 Correct 1798 ms 37544 KB Output is correct
93 Correct 1571 ms 39776 KB Output is correct
94 Correct 3766 ms 30708 KB Output is correct
95 Correct 3574 ms 30772 KB Output is correct
96 Correct 3712 ms 30620 KB Output is correct
97 Correct 4363 ms 30580 KB Output is correct
98 Correct 4216 ms 29736 KB Output is correct
99 Correct 4215 ms 29736 KB Output is correct
100 Correct 4397 ms 29616 KB Output is correct
101 Correct 4859 ms 29612 KB Output is correct
102 Correct 278 ms 29588 KB Output is correct
103 Correct 310 ms 29688 KB Output is correct
104 Correct 1351 ms 29544 KB Output is correct
105 Correct 124 ms 29852 KB Output is correct
106 Correct 138 ms 29712 KB Output is correct
107 Correct 3563 ms 29784 KB Output is correct
108 Correct 3631 ms 29668 KB Output is correct