codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1042.md (9367B)


      1 Source: https://codeforces.com/blog/entry/61891
      2 
      3 [1042A - Benches](/contest/1042/problem/A "Codeforces Round 510 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <set>
     13 #include <algorithm>
     14 #include <iostream>
     15 #include <vector>
     16 #include <string>
     17 #include <cassert>
     18 
     19 using namespace std;
     20 
     21 const int N = 100 + 13;
     22 
     23 int n, m;
     24 int a[N];
     25 
     26 int main() {
     27     cin >> n >> m;
     28     for (int i = 0; i < n; i++) {
     29         cin >> a[i];
     30     }
     31     int ans2 = *max_element(a, a + n) + m;
     32     for (int it = 0; it < m; it++) {
     33         int pos = -1;
     34         for (int i = 0; i < n; i++) {
     35             if (pos == -1 || a[i] < a[pos]) {
     36                 pos = i;
     37             }
     38         }
     39         assert(pos != -1);
     40         a[pos]++;
     41     }
     42     int ans1 = *max_element(a, a + n);
     43     cout << ans1 << ' ' << ans2 << endl;
     44 }
     45 ```
     46 
     47 [1042B - Vitamins](/contest/1042/problem/B "Codeforces Round 510 (Div. 2)")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution**
     54 
     55 ```
     56 #include <bits/stdc++.h>
     57 
     58 using namespace std;
     59 
     60 const int INF = 1e9;
     61 
     62 int n;
     63 map<string, int> was;
     64 
     65 inline void read() {	
     66 	cin >> n;
     67 	for (int i = 0; i < n; i++) {
     68 		int c;
     69 		string s;
     70 		cin >> c >> s;
     71 		sort(s.begin(), s.end());
     72 		if (was.count(s) == 0) {
     73 			was[s] = c;
     74 		} else {
     75 			was[s] = min(was[s], c);
     76 		}
     77 	}
     78 }
     79 
     80 inline int getC(string a, string b) {
     81  	if (!was.count(a) || !was.count(b)) {
     82  		return INF;
     83  	}
     84  	return was[a] + was[b];
     85 }
     86 
     87 inline void solve() {
     88 	int ans = INF;
     89 	if (was.count("A") && was.count("B") && was.count("C")) {
     90 		ans = was["A"] + was["B"] + was["C"];
     91 	}
     92     if (was.count("ABC")) {
     93     	ans = min(ans, was["ABC"]);
     94     }
     95     ans = min(ans, getC("AB", "C"));
     96     ans = min(ans, getC("A", "BC"));
     97     ans = min(ans, getC("AC", "B"));
     98     ans = min(ans, getC("AB", "BC"));
     99     ans = min(ans, getC("AC", "BC"));
    100     ans = min(ans, getC("AC", "AB"));
    101     if (ans == INF) {
    102     	ans = -1;
    103     }
    104     cout << ans << endl;
    105 }
    106 
    107 int main () {
    108     read();
    109     solve();
    110 }
    111 ```
    112 
    113 [1042C - Array Product](/contest/1042/problem/C "Codeforces Round 510 (Div. 2)")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 int main() {
    127 #ifdef _DEBUG
    128 	freopen("input.txt", "r", stdin);
    129 //	freopen("output.txt", "w", stdout);
    130 #endif
    131 	
    132 	int n;
    133 	scanf("%d", &n);
    134 	vector<int> a(n);
    135 	for (int i = 0; i < n; ++i)
    136 		scanf("%d", &a[i]);
    137 	
    138 	int cntneg = 0;
    139 	int cntzero = 0;
    140 	vector<int> used(n);
    141 	int pos = -1;
    142 	for (int i = 0; i < n; ++i) {
    143 		if (a[i] == 0) {
    144 			used[i] = 1;
    145 			++cntzero;
    146 		}
    147 		if (a[i] < 0) {
    148 			++cntneg;
    149 			if (pos == -1 || abs(a[pos]) > abs(a[i]))
    150 				pos = i;
    151 		}
    152 	}
    153 	if (cntneg & 1)
    154 		used[pos] = 1;
    155 		
    156 	if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) {
    157 		for (int i = 0; i < n - 1; ++i)
    158 			printf("1 %d %d\n", i + 1, i + 2);
    159 		return 0;
    160 	}
    161 	
    162 	int lst = -1;
    163 	for (int i = 0; i < n; ++i) {
    164 		if (used[i]) {
    165 			if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1);
    166 			lst = i;
    167 		}
    168 	}
    169 	if (lst != -1) printf("2 %d\n", lst + 1);
    170 	
    171 	lst = -1;
    172 	for (int i = 0; i < n; ++i) {
    173 		if (!used[i]) {
    174 			if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1);
    175 			lst = i;
    176 		}
    177 	}
    178 	
    179 	return 0;
    180 }
    181 ```
    182 
    183 [1042D - Petya and Array](/contest/1042/problem/D "Codeforces Round 510 (Div. 2)")
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Solution**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 
    194 #define forn(i, n) for (int i = 0; i < int(n); i++)
    195 
    196 using namespace std;
    197 
    198 const int N = 200 * 1000 + 13;
    199 
    200 int n;
    201 long long T;
    202 int a[N];
    203 int f[N];
    204 
    205 void upd(int x){
    206 	for (int i = x; i < N; i |= i + 1)
    207 		++f[i];
    208 }
    209 
    210 int get(int x){
    211 	int res = 0;
    212 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    213 		res += f[i];
    214 	return res;
    215 }
    216 
    217 int main() {
    218 	scanf("%d%lld", &n, &T);
    219 	forn(i, n)
    220 		scanf("%d", &a[i]);
    221 	
    222 	vector<long long> sums(1, 0ll);
    223 	long long pr = 0;
    224 	forn(i, n){
    225 		pr += a[i];
    226 		sums.push_back(pr);
    227 	}
    228 	
    229 	sort(sums.begin(), sums.end());
    230 	sums.resize(unique(sums.begin(), sums.end()) - sums.begin());
    231 	
    232 	long long ans = 0;
    233 	pr = 0;
    234 	upd(lower_bound(sums.begin(), sums.end(), 0ll) - sums.begin());
    235 	
    236 	forn(i, n){
    237 		pr += a[i];
    238 		
    239 		int npos = upper_bound(sums.begin(), sums.end(), pr - T) - sums.begin();
    240 		ans += (i + 1 - get(npos - 1));
    241 		
    242 		int k = lower_bound(sums.begin(), sums.end(), pr) - sums.begin();
    243 		upd(k);
    244 	}
    245 	
    246 	printf("%lld\n", ans);
    247 	return 0;
    248 }
    249 ```
    250 
    251 [1042E - Vasya and Magic Matrix](/contest/1042/problem/E "Codeforces Round 510 (Div. 2)")
    252 
    253 **Tutorial**
    254 
    255 Tutorial is loading...
    256 
    257 **Solution**
    258 
    259 ```
    260 #include<bits/stdc++.h>
    261 
    262 using namespace std;
    263 
    264 const int MOD = 998244353;
    265 const int N = 1009;
    266 
    267 int mul(int a, int b){
    268 	return int(a * 1LL * b % MOD);
    269 }
    270 
    271 void upd(int &a, int b){
    272 	a += b;
    273 	while(a >= MOD) a -= MOD;
    274 	while(a < 0) a += MOD;
    275 }
    276 
    277 int bp(int a, int n){
    278 	int res = 1;
    279 	for(; n > 0; n >>= 1){
    280 		if(n & 1) res = mul(res, a);
    281 		a = mul(a, a);
    282 	}
    283 	
    284 	return res;
    285 }
    286 
    287 int inv(int a){
    288 	int ia = bp(a, MOD - 2);
    289 	assert(mul(a, ia) == 1);
    290 	return ia;
    291 }
    292 
    293 int n, m;
    294 int a[N][N];
    295 int dp[N][N];
    296 int si, sj;
    297 
    298 int main() {
    299 	//freopen("input.txt", "r", stdin);
    300 	scanf("%d %d", &n, &m);
    301 	for(int i = 0; i < n; ++i) 
    302 		for(int j = 0; j < m; ++j)
    303 			scanf("%d", &a[i][j]);
    304 	scanf("%d %d", &si, &sj);
    305 	--si, --sj;
    306 	
    307 	vector <pair<int, pair<int, int> > > v;
    308 	for(int i = 0; i < n; ++i)
    309 		for(int j = 0; j < m; ++j)
    310 			v.push_back(make_pair(a[i][j], make_pair(i, j)));
    311 
    312 	sort(v.begin(), v.end());
    313 	int l = 0;
    314 	int sumDP = 0, sumX = 0, sumY = 0, sumX2 = 0, sumY2 = 0;
    315 	while(l < int(v.size())){
    316 		int r = l;
    317 		while(r < int(v.size()) && v[r].first == v[l].first) ++r;
    318 		
    319 		int il = -1;
    320 		if(l != 0) il = inv(l);
    321 		for(int i = l; i < r; ++i){
    322 			int x = v[i].second.first, y = v[i].second.second;
    323 			if(il == -1){
    324 				dp[x][y] = 0;
    325 				continue;
    326 			}
    327 			
    328 			
    329 			upd(dp[x][y], mul(sumDP, il));
    330 			
    331 			upd(dp[x][y], mul(x, x));
    332 			upd(dp[x][y], mul(y, y));
    333 			
    334 			upd(dp[x][y], mul(sumX2, il));
    335 			upd(dp[x][y], mul(sumY2, il));
    336 			
    337 			upd(dp[x][y], mul(mul(-x - x, sumX), il));
    338 			upd(dp[x][y], mul(mul(-y - y, sumY), il));		
    339 		}
    340 		
    341 		for(int i = l; i < r; ++i){
    342 			int x = v[i].second.first, y = v[i].second.second;
    343 			
    344 			upd(sumDP, dp[x][y]);
    345 			
    346 			upd(sumX2, mul(x, x));
    347 			upd(sumY2, mul(y, y));
    348 			
    349 			upd(sumX, x);
    350 			upd(sumY, y);
    351 		}
    352 		
    353 		l = r;
    354 		
    355 	}
    356 	
    357 	printf("%d\n", dp[si][sj]);
    358 	return 0;
    359 }
    360 ```
    361 
    362 [1042F - Leaf Sets](/contest/1042/problem/F "Codeforces Round 510 (Div. 2)")
    363 
    364 **Tutorial**
    365 
    366 Tutorial is loading...
    367 
    368 **Solution (O(n log n))**
    369 
    370 ```
    371 #include <bits/stdc++.h>
    372 
    373 using namespace std;
    374 
    375 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    376 #define sz(a) int((a).size())
    377 
    378 const int N = 1000 * 1000 + 13;
    379 
    380 int n, k;
    381 vector<int> g[N];
    382 int ans;
    383 
    384 int dfs(int v, int p = -1){
    385 	if (g[v].size() == 1)
    386 		return 0;
    387 	
    388 	vector<int> cur;
    389 	for (auto u : g[v]){
    390 		if (u == p) continue;
    391 		cur.push_back(dfs(u, v) + 1);
    392 	}
    393 	sort(cur.begin(), cur.end());
    394 	
    395 	while (sz(cur) >= 2){
    396 		if (cur.back() + cur[sz(cur) - 2] <= k)
    397 			break;
    398 		++ans;
    399 		cur.pop_back();
    400 	}
    401 	
    402 	return cur.back();
    403 }
    404 
    405 int main(){
    406 	scanf("%d%d", &n, &k);
    407 	forn(i, n - 1){
    408 		int v, u;
    409 		scanf("%d%d", &v, &u);
    410 		--v, --u;
    411 		g[v].push_back(u);
    412 		g[u].push_back(v);
    413 	}
    414 	
    415 	forn(i, n){
    416 		if (sz(g[i]) > 1){
    417 			dfs(i);
    418 			break;
    419 		}
    420 	}
    421 	
    422 	printf("%d\n", ans + 1);
    423 	return 0;
    424 }
    425 ```
    426 
    427 **Solution (Small to Large, O(n log^2 n))**
    428 
    429 ```
    430 #include <bits/stdc++.h>
    431 
    432 using namespace std;
    433 
    434 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    435 #define sz(a) int((a).size())
    436 
    437 const int N = 1000 * 1000 + 13;
    438 
    439 int n, k;
    440 vector<int> g[N];
    441 multiset<int> val[N];
    442 int ans;
    443 
    444 void dfs(int v, int d, int p){
    445 	if (g[v].size() == 1){
    446 		val[v].insert(d);
    447 		return;
    448 	}
    449 	
    450 	int bst = -1;
    451 	for (auto u : g[v]){
    452 		if (u == p) continue;
    453 		dfs(u, d + 1, v);
    454 		if (bst == -1 || sz(val[u]) > sz(val[bst]))
    455 			bst = u;
    456 	}
    457 	swap(val[bst], val[v]);
    458 	
    459 	for (auto u : g[v]){
    460 		if (u == p || u == bst) continue;
    461 		for (auto it : val[u]){
    462 			int dd = k + 2 * d - it;
    463 			auto jt = val[v].upper_bound(dd);
    464 			if (jt == val[v].begin()){
    465 				val[v].insert(it);
    466 			}
    467 			else{
    468 				--jt;
    469 				int t = *jt;
    470 				val[v].erase(jt);
    471 				val[v].insert(max(it, t));
    472 			}
    473 		}
    474 	}
    475 }
    476 
    477 int main(){
    478 	scanf("%d%d", &n, &k);
    479 	forn(i, n - 1){
    480 		int v, u;
    481 		scanf("%d%d", &v, &u);
    482 		--v, --u;
    483 		g[v].push_back(u);
    484 		g[u].push_back(v);
    485 	}
    486 	
    487 	forn(i, n){
    488 		if (sz(g[i]) > 1){
    489 			dfs(i, 0, -1);
    490 			printf("%d\n", sz(val[i]));
    491 			break;
    492 		}
    493 	}
    494 	return 0;
    495 }
    496 ```
    497 
    498 **Solution (O(n))**
    499 
    500 ```
    501 #include <bits/stdc++.h>
    502 
    503 using namespace std;
    504 
    505 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    506 #define sz(a) int((a).size())
    507 
    508 const int N = 1000 * 1000 + 13;
    509 
    510 int n, k;
    511 vector<int> g[N];
    512 int ans;
    513 
    514 int dfs(int v, int p = -1){
    515 	if (g[v].size() == 1)
    516 		return 0;
    517 	
    518 	vector<int> cur;
    519 	for (auto u : g[v]){
    520 		if (u == p) continue;
    521 		cur.push_back(dfs(u, v) + 1);
    522 	}
    523 	
    524 	int pos = -1;
    525 	forn(i, sz(cur)) {
    526 		if (cur[i] * 2 <= k && (pos == -1 || cur[pos] < cur[i]))
    527 			pos = i;
    528 	}
    529 	
    530 	if (pos == -1) {
    531 		ans += sz(cur) - 1;
    532 		return *min_element(cur.begin(), cur.end());
    533 	}
    534 	
    535 	int res = -1;
    536 	forn(i, sz(cur)) {
    537 		if (cur[pos] >= cur[i]) continue;
    538 		if (cur[i] + cur[pos] <= k && (res == -1 || cur[i] < cur[res]))
    539 			res = i;
    540 	}
    541 	
    542 	forn(i, sz(cur))
    543 		ans += (cur[i] > cur[pos]);
    544 	if (res != -1)
    545 		--ans;
    546 	
    547 	return (res == -1 ? cur[pos] : cur[res]);
    548 }
    549 
    550 int main(){
    551 	scanf("%d%d", &n, &k);
    552 	forn(i, n - 1) {
    553 		int v, u;
    554 		scanf("%d%d", &v, &u);
    555 		--v, --u;
    556 		g[v].push_back(u);
    557 		g[u].push_back(v);
    558 	}
    559 	
    560 	forn(i, n) {
    561 		if (sz(g[i]) > 1) {
    562 			dfs(i);
    563 			break;
    564 		}
    565 	}
    566 	
    567 	printf("%d\n", ans + 1);
    568 	return 0;
    569 }
    570 ```