codeforces-scrape

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

1092.md (7782B)


      1 Source: https://codeforces.com/blog/entry/63961
      2 
      3 [1092A - Uniform String](/contest/1092/problem/A "Codeforces Round 527 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int t;
     23 	cin >> t;
     24 	for (int i = 0; i < t; ++i) {
     25 		int n, k;
     26 		cin >> n >> k;
     27 		for (int j = 0; j < n; ++j) {
     28 			cout << char('a' + j % k);
     29 		}
     30 		cout << endl;
     31 	}
     32 	
     33 	return 0;
     34 }
     35 ```
     36 
     37 [1092B - Teams Forming](/contest/1092/problem/B "Codeforces Round 527 (Div. 3)")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 using namespace std;
     49 
     50 int main() {
     51 #ifdef _DEBUG
     52 	freopen("input.txt", "r", stdin);
     53 //	freopen("output.txt", "w", stdout);
     54 #endif
     55 	
     56 	int n;
     57 	cin >> n;
     58 	vector<int> a(n);
     59 	for (int i = 0; i < n; ++i) {
     60 		cin >> a[i];
     61 	}
     62 	
     63 	sort(a.begin(), a.end());
     64 	int res = 0;
     65 	for (int i = 0; i < n; i += 2) {
     66 		res += a[i + 1] - a[i];
     67 	}
     68 	
     69 	cout << res << endl;
     70 	
     71 	return 0;
     72 }
     73 ```
     74 
     75 [1092C - Prefixes and Suffixes](/contest/1092/problem/C "Codeforces Round 527 (Div. 3)")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85 
     86 using namespace std;
     87 
     88 int n;
     89 vector<string> v;
     90 
     91 string res;
     92 
     93 bool check(const string &pref, const string &suf) {
     94 	string s = pref + suf.substr(n - 2);
     95 	multiset<string> vv, sPref, sSuf;
     96 	for (int i = 0; i < n - 1; ++i) {
     97 		sPref.insert(s.substr(0, n - i - 1));
     98 		vv.insert(s.substr(0, n - i - 1));
     99 		sSuf.insert(s.substr(i + 1));
    100 		vv.insert(s.substr(i + 1));
    101 	}
    102 	if (vv == multiset<string>(v.begin(), v.end())) {
    103 		for (int i = 0; i < 2 * n - 2; ++i) {
    104 			if (sPref.count(v[i])) {
    105 				res += 'P';
    106 				sPref.erase(sPref.find(v[i]));
    107 			} else if (sSuf.count(v[i])) {
    108 				res += 'S';
    109 				sSuf.erase(sSuf.find(v[i]));
    110 			} else {
    111 				assert(false);
    112 			}
    113 		}
    114 		return true;
    115 	}
    116 	return false;
    117 }
    118 
    119 int main() {
    120 #ifdef _DEBUG
    121 	freopen("input.txt", "r", stdin);
    122 //	freopen("output.txt", "w", stdout);
    123 #endif
    124 	
    125 	cin >> n;
    126 	v = vector<string>(2 * n - 2);
    127 	vector<string> big;
    128 	for (int i = 0; i < 2 * n - 2; ++i) {
    129 		cin >> v[i];
    130 		if (int(v[i].size()) == n - 1) {
    131 			big.push_back(v[i]);
    132 		}
    133 	}
    134 	
    135 	if (check(big[0], big[1])) {
    136 		cout << res << endl;
    137 	} else {
    138 		check(big[1], big[0]);
    139 		cout << res << endl;
    140 	}
    141 	
    142 	return 0;
    143 }
    144 ```
    145 
    146 [1092D1 - Great Vova Wall (Version 1)](/contest/1092/problem/D1 "Codeforces Round 527 (Div. 3)")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution 1**
    153 
    154 ```
    155 #include <bits/stdc++.h>
    156 
    157 #define forn(i, n) for (int i = 0; i < int(n); i++)
    158 
    159 using namespace std;
    160 
    161 const int N = 200 * 1000 + 13;
    162 
    163 int n;
    164 int a[N];
    165 
    166 int main() {
    167 	scanf("%d", &n);
    168 	forn(i, n){
    169 		scanf("%d", &a[i]);
    170 		a[i] &= 1;
    171 	}
    172 	
    173 	vector<int> st;
    174 	forn(i, n){
    175 		if (!st.empty() && a[i] == st.back())
    176 			st.pop_back();
    177 		else
    178 			st.push_back(a[i]);
    179 	}
    180 	
    181 	puts(st.size() <= 1 ? "YES" : "NO");
    182 	return 0;
    183 }
    184 ```
    185 
    186 **Solution 2**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 #define forn(i, n) for (int i = 0; i < int(n); i++)
    192 
    193 using namespace std;
    194 
    195 const int N = 200 * 1000 + 13;
    196 
    197 int n;
    198 int a[N];
    199 
    200 int main() {
    201 	scanf("%d", &n);
    202 	forn(i, n){
    203 		scanf("%d", &a[i]);
    204 		a[i] &= 1;
    205 	}
    206 	
    207 	set<pair<int, int>> seg, even;
    208 	forn(i, n){
    209 		int j = i;
    210 		while (j + 1 < n && a[j + 1] == a[i]) ++j;
    211 		seg.insert({i, j});
    212 		if ((j - i + 1) % 2 == 0)
    213 			even.insert({i, j});
    214 		i = j;
    215 	}
    216 	
    217 	while (seg.size() > 1 && !even.empty()){
    218 		auto cur = *even.begin();
    219 		even.erase(cur);
    220 		seg.erase(cur);
    221 		auto it = seg.lower_bound(cur);
    222 		if (it != seg.end()){
    223 			cur.second = it->second;
    224 			if ((it->second - it->first + 1) % 2 == 0)
    225 				even.erase(*it);
    226 			seg.erase(it);
    227 		}
    228 		it = seg.lower_bound(cur);
    229 		if (it != seg.begin()){
    230 			--it;
    231 			cur.first = it->first;
    232 			if ((it->second - it->first + 1) % 2 == 0)
    233 				even.erase(*it);
    234 			seg.erase(it);
    235 		}
    236 		seg.insert(cur);
    237 		if ((cur.second - cur.first + 1) % 2 == 0)
    238 			even.insert(cur);
    239 	}
    240 	
    241 	puts(seg.size() == 1 ? "YES" : "NO");
    242 	return 0;
    243 }
    244 ```
    245 
    246 [1092D2 - Great Vova Wall (Version 2)](/contest/1092/problem/D2 "Codeforces Round 527 (Div. 3)")
    247 
    248 **Tutorial**
    249 
    250 Tutorial is loading...
    251 
    252 **Solution**
    253 
    254 ```
    255 #include <bits/stdc++.h>
    256 
    257 #define forn(i, n) for (int i = 0; i < int(n); i++)
    258 
    259 using namespace std;
    260 
    261 const int N = 1000 * 1000 + 13;
    262 
    263 int n;
    264 int a[N];
    265 
    266 int main() {
    267 	scanf("%d", &n);
    268 	forn(i, n) scanf("%d", &a[i]);
    269 	vector<int> st;
    270 	
    271 	int mx = *max_element(a, a + n);
    272 	
    273 	forn(i, n){
    274 		if (a[i] == mx) continue;
    275 		
    276 		int j = i - 1;
    277 		while (j + 1 < n && a[j + 1] != mx){
    278 			++j;
    279 			if (!st.empty() && st.back() == a[j]){
    280 				st.pop_back();
    281 			}
    282 			else if (st.empty() || st.back() > a[j]){
    283 				st.push_back(a[j]);
    284 			}
    285 			else{
    286 				puts("NO");
    287 				return 0;
    288 			}
    289 		}
    290 		
    291 		if (!st.empty()){
    292 			puts("NO");
    293 			return 0;
    294 		}
    295 		
    296 		i = j;
    297 	}
    298 	
    299 	puts("YES");
    300 	return 0;
    301 }
    302 ```
    303 
    304 [1092E - Minimal Diameter Forest](/contest/1092/problem/E "Codeforces Round 527 (Div. 3)")
    305 
    306 **Tutorial**
    307 
    308 Tutorial is loading...
    309 
    310 **Solution**
    311 
    312 ```
    313 #include <bits/stdc++.h>
    314 
    315 #define forn(i, n) for (int i = 0; i < int(n); i++)
    316 
    317 using namespace std;
    318 
    319 const int N = 200 * 1000 + 13;
    320 const int INF = 1000000000;
    321 
    322 int n, m;
    323 vector<int> g[N];
    324 
    325 int bfs(int x, int dist[N]){
    326 	queue<int> q;
    327 	q.push(x);
    328 	dist[x] = 0;
    329 	int lst = -1;
    330 	while (!q.empty()){
    331 		int v = q.front();
    332 		q.pop();
    333 		lst = v;
    334 		for (auto u : g[v]) if (dist[u] > dist[v] + 1){
    335 			dist[u] = dist[v] + 1;
    336 			q.push(u);
    337 		}
    338 	}
    339 	return lst;
    340 }
    341 
    342 int distx[N], disty[N];
    343 bool used[N];
    344 vector<int> cur;
    345 
    346 void dfs(int v){
    347 	used[v] = true;
    348 	cur.push_back(v);
    349 	for (auto u : g[v]) if (!used[u])
    350 		dfs(u);
    351 }
    352 
    353 int main() {
    354 	scanf("%d%d", &n, &m);
    355 	forn(i, m){
    356 		int v, u;
    357 		scanf("%d%d", &v, &u);
    358 		--v, --u;
    359 		g[v].push_back(u);
    360 		g[u].push_back(v);
    361 	}
    362 	
    363 	forn(i, n) distx[i] = disty[i] = INF;
    364 	
    365 	vector<pair<int, int>> comps;
    366 	forn(i, n) if (!used[i]){
    367 		cur.clear();
    368 		dfs(i);
    369 		int x = bfs(i, distx);
    370 		int y = bfs(x, disty);
    371 		for (auto v : cur) distx[v] = INF;
    372 		bfs(y, distx);
    373 		int d = disty[y], center;
    374 		for (auto v : cur) if (distx[v] == d / 2 && disty[v] == d - d / 2)
    375 			center = v;
    376 		comps.push_back({d, center});
    377 	}
    378 	
    379 	vector<pair<int, int>> ans;
    380 	nth_element(comp.begin(), comp.end() - 1, comp.end());
    381 	forn(i, int(comps.size()) - 1){
    382 		g[comps[i].second].push_back(comps.back().second);
    383 		g[comps.back().second].push_back(comps[i].second);
    384 		ans.push_back({comps[i].second, comps.back().second});
    385 	}
    386 	
    387 	forn(i, n) distx[i] = disty[i] = INF;
    388 	int y = bfs(bfs(comps.back().second, distx), disty);
    389 	
    390 	printf("%d\n", disty[y]);
    391 	for (auto it : ans)
    392 		printf("%d %d\n", it.first + 1, it.second + 1);
    393 	return 0;
    394 }
    395 ```
    396 
    397 [1092F - Tree with Maximum Cost](/contest/1092/problem/F "Codeforces Round 527 (Div. 3)")
    398 
    399 **Tutorial**
    400 
    401 Tutorial is loading...
    402 
    403 **Solution**
    404 
    405 ```
    406 #include <bits/stdc++.h>
    407 
    408 using namespace std;
    409 
    410 long long res, ans;
    411 
    412 vector<int> a;
    413 vector<long long> sum;
    414 vector<vector<int>> g;
    415 
    416 void dfs(int v, int p = -1, int h = 0) {
    417 	res += h * 1ll * a[v];
    418 	sum[v] = a[v];
    419 	
    420 	for (auto to : g[v]) {
    421 		if (to == p) {
    422 			continue;
    423 		}
    424 		dfs(to, v, h + 1);
    425 		sum[v] += sum[to];
    426 	}
    427 }
    428 
    429 void go(int v, int p = -1) {
    430 	ans = max(ans, res);
    431 	
    432 	for (auto to : g[v]) {
    433 		if (to == p) {
    434 			continue;
    435 		}
    436 		
    437 		res -= sum[to];
    438 		sum[v] -= sum[to];
    439 		res += sum[v];
    440 		sum[to] += sum[v];
    441 		
    442 		go(to, v);
    443 		
    444 		sum[to] -= sum[v];
    445 		res -= sum[v];
    446 		sum[v] += sum[to];
    447 		res += sum[to];
    448 	}
    449 }
    450 
    451 int main() {
    452 #ifdef _DEBUG
    453 	freopen("input.txt", "r", stdin);
    454 //	freopen("output.txt", "w", stdout);
    455 #endif
    456 	
    457 	int n;
    458 	cin >> n;
    459 	a = vector<int>(n);
    460 	sum = vector<long long>(n);
    461 	g = vector<vector<int>>(n);
    462 	for (int i = 0; i < n; ++i) {
    463 		cin >> a[i];
    464 	}
    465 	for (int i = 0; i < n - 1; ++i) {
    466 		int x, y;
    467 		cin >> x >> y;
    468 		--x, --y;
    469 		g[x].push_back(y);
    470 		g[y].push_back(x);
    471 	}
    472 	
    473 	dfs(0);
    474 	go(0);
    475 	
    476 	cout << ans << endl;
    477 	
    478 	return 0;
    479 }
    480 ```