codeforces-scrape

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

1555.md (8255B)


      1 Source: https://codeforces.com/blog/entry/93389
      2 
      3 [1555A - PizzaForces](/contest/1555/problem/A "Educational Codeforces Round 112 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     long long n;
     23     cin >> n;
     24     cout << max(6LL, n + 1) / 2 * 5 << '\n';
     25   }
     26 }
     27 ```
     28 
     29 [1555B - Two Tables](/contest/1555/problem/B "Educational Codeforces Round 112 (Rated for Div. 2)")
     30 
     31 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution (adedalic)**
     38 
     39 ```
     40 #include<bits/stdc++.h>
     41 
     42 using namespace std;
     43 
     44 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     45 #define sz(a) int((a).size())
     46 
     47 #define x first
     48 #define y second
     49 
     50 typedef long long li;
     51 typedef pair<int, int> pt;
     52 
     53 const int INF = int(1e9);
     54 
     55 int W, H;
     56 int x1, y1, x2, y2;
     57 int w, h;
     58 
     59 inline bool read() {
     60 	if(!(cin >> W >> H))
     61 		return false;
     62 	cin >> x1 >> y1 >> x2 >> y2;
     63 	cin >> w >> h;
     64 	return true;
     65 }
     66 
     67 inline void solve() {
     68 	int ans = INF;
     69 	if (x2 - x1 + w <= W) {
     70 		ans = min(ans, max(0, w - x1));
     71 		ans = min(ans, max(0, x2 - (W - w)));
     72 	}
     73 	if (y2 - y1 + h <= H) {
     74 		ans = min(ans, max(0, h - y1));
     75 		ans = min(ans, max(0, y2 - (H - h)));
     76 	}
     77 	if (ans == INF)
     78 		cout << -1 << endl;
     79 	else
     80 		cout << double(ans) << endl;
     81 }
     82 
     83 int main() {
     84 #ifdef _DEBUG
     85 	freopen("input.txt", "r", stdin);
     86 #endif	
     87 	cout << fixed << setprecision(9);
     88 	int t; cin >> t;
     89 	while(t--) {
     90 		(read());
     91 		solve();
     92 	}
     93 	return 0;
     94 }
     95 ```
     96 
     97 [1555C - Coin Rows](/contest/1555/problem/C "Educational Codeforces Round 112 (Rated for Div. 2)")
     98 
     99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (awoo)**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 
    110 #define forn(i, n) for (int i = 0; i < int(n); i++)
    111 
    112 using namespace std;
    113 
    114 const int INF = 2e9 + 10;
    115 
    116 int main() {
    117 	int t;
    118 	scanf("%d", &t);
    119 	forn(_, t){
    120 		int n;
    121 		scanf("%d", &n);
    122 		vector<vector<int>> a(2, vector<int>(n));
    123 		forn(i, 2) forn(j, n)
    124 			scanf("%d", &a[i][j]);
    125 		int ans = INF;
    126 		int sum1 = 0, sum2 = 0;
    127 		forn(i, n) sum1 += a[0][i];
    128 		forn(i, n){
    129 			sum1 -= a[0][i];
    130 			ans = min(ans, max(sum1, sum2));
    131 			sum2 += a[1][i];
    132 		}
    133 		printf("%d\n", ans);
    134 	}
    135 }
    136 ```
    137 
    138 [1555D - Say No to Palindromes](/contest/1555/problem/D "Educational Codeforces Round 112 (Rated for Div. 2)")
    139 
    140 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution (Neon)**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150 
    151 using namespace std;
    152 
    153 int main() {
    154   ios_base::sync_with_stdio(false);
    155   cin.tie(NULL); 
    156   int n, m;
    157   cin >> n >> m;
    158   string s;
    159   cin >> s;
    160   vector<vector<int>> pr(6, vector<int>(n + 1));
    161   string t = "abc";
    162   int cur = 0;
    163   do {
    164     for (int i = 0; i < n; ++i)
    165       pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
    166     ++cur;
    167   } while (next_permutation(t.begin(), t.end()));
    168   while (m--) {
    169     int l, r;
    170     cin >> l >> r;
    171     int ans = n;
    172     for (int i = 0; i < 6; ++i)
    173       ans = min(ans, pr[i][r] - pr[i][l - 1]);
    174     cout << ans << "\n";
    175   }
    176 }
    177 ```
    178 
    179 [1555E - Boring Segments](/contest/1555/problem/E "Educational Codeforces Round 112 (Rated for Div. 2)")
    180 
    181 Idea: [vovuh](/profile/vovuh "Master vovuh"), [adedalic](/profile/adedalic "International Master adedalic")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution (awoo)**
    188 
    189 ```
    190 #include <bits/stdc++.h>
    191 
    192 #define forn(i, n) for (int i = 0; i < int(n); i++)
    193 
    194 using namespace std;
    195 
    196 const int INF = 1e9;
    197 
    198 vector<int> t, ps;
    199 
    200 void push(int v){
    201 	if (v * 2 + 1 < int(ps.size())){
    202 		ps[v * 2] += ps[v];
    203 		ps[v * 2 + 1] += ps[v];
    204 	}
    205 	t[v] += ps[v];
    206 	ps[v] = 0;
    207 }
    208 
    209 void upd(int v, int l, int r, int L, int R, int val){
    210 	push(v);
    211 	if (L >= R)
    212 		return;
    213 	if (l == L && r == R){
    214 		ps[v] += val;
    215 		push(v);
    216 		return;
    217 	}
    218 	int m = (l + r) / 2;
    219 	upd(v * 2, l, m, L, min(m, R), val);
    220 	upd(v * 2 + 1, m, r, max(m, L), R, val);
    221 	t[v] = min(t[v * 2], t[v * 2 + 1]);
    222 }
    223 
    224 int get(){
    225 	return t[1] + ps[1];
    226 }
    227 
    228 struct seg{
    229 	int l, r, w;
    230 };
    231 
    232 int main() {
    233 	int n, m;
    234 	scanf("%d%d", &n, &m);
    235 	vector<seg> a(n);
    236 	forn(i, n){
    237 		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
    238 		--a[i].l, --a[i].r;
    239 	}
    240 	--m;
    241 	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
    242 		return a.w < b.w;
    243 	});
    244 	t.resize(4 * m);
    245 	ps.resize(4 * m);
    246 	int ans = INF;
    247 	int j = 0;
    248 	forn(i, n){
    249 		while (j < n && get() == 0){
    250 			upd(1, 0, m, a[j].l, a[j].r, 1);
    251 			++j;
    252 		}
    253 		if (get() == 0){
    254 			break;
    255 		}
    256 		ans = min(ans, a[j - 1].w - a[i].w);
    257 		upd(1, 0, m, a[i].l, a[i].r, -1);
    258 	}
    259 	printf("%d\n", ans);
    260 	return 0;
    261 }
    262 ```
    263 
    264 [1555F - Good Graph](/contest/1555/problem/F "Educational Codeforces Round 112 (Rated for Div. 2)")
    265 
    266 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution (adedalic)**
    273 
    274 ```
    275 #include<bits/stdc++.h>
    276 
    277 using namespace std;
    278 
    279 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    280 #define sz(a) int((a).size())
    281 
    282 #define x first
    283 #define y second
    284 
    285 typedef long long li;
    286 typedef pair<int, int> pt;
    287 
    288 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    289 	return out << "(" << p.x << ", " << p.y << ")";
    290 }
    291 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    292 	fore(i, 0, sz(v)) {
    293 		if(i) out << " ";
    294 		out << v[i];
    295 	}
    296 	return out;
    297 }
    298 
    299 const int INF = int(1e9);
    300 const li INF64 = li(1e18);
    301 
    302 int n, q;
    303 vector< array<int, 3> > es;
    304 
    305 inline bool read() {
    306 	if(!(cin >> n >> q))
    307 		return false;
    308 	es.resize(q);
    309 	fore (i, 0, q) {
    310 		cin >> es[i][0] >> es[i][1] >> es[i][2];
    311 		es[i][0]--;
    312 		es[i][1]--;
    313 	}
    314 	return true;
    315 }
    316 
    317 vector< vector<pt> > g;
    318 
    319 const int LOG = 19;
    320 vector<int> up[LOG];
    321 vector<int> tin, tout;
    322 vector<int> xr;
    323 int T = 0;
    324 
    325 void dfs(int v, int p, int curXor) {
    326 	tin[v] = T++;
    327 	xr[v] = curXor;
    328 	up[0][v] = p;
    329 	fore (pw, 1, LOG)
    330 		up[pw][v] = up[pw - 1][up[pw - 1][v]];
    331 	
    332 	for (auto [to, w] : g[v]) {
    333 		if (to == p)
    334 			continue;
    335 		dfs(to, v, curXor ^ w);
    336 	}
    337 	tout[v] = T;
    338 }
    339 
    340 void buildLCA() {
    341 	fore (pw, 0, LOG)
    342 		up[pw].resize(n);
    343 	tin.assign(n, -1);
    344 	tout.assign(n, -1);
    345 	xr.assign(n, 0);
    346 	
    347 	T = 0;
    348 	fore (v, 0, n) {
    349 		if (tin[v] != -1)
    350 			continue;
    351 		dfs(v, v, 0);
    352 	}
    353 }
    354 
    355 int isPar(int p, int v) {
    356 	return tin[p] <= tin[v] && tout[v] <= tout[p];
    357 }
    358 
    359 int lca(int u, int v) {
    360 	if (isPar(u, v)) return u;
    361 	if (isPar(v, u)) return v;
    362 	
    363 	for (int pw = LOG - 1; pw >= 0; pw--) {
    364 		if (!isPar(up[pw][v], u))
    365 			v = up[pw][v];
    366 	}
    367 	return up[0][v];
    368 }
    369 
    370 vector<int> par, rk;
    371 
    372 void init(int n) {
    373 	par.assign(n, 0);
    374 	iota(par.begin(), par.end(), 0);
    375 	rk.assign(n, 1);
    376 }
    377 
    378 int top(int v) {
    379 	if (par[v] != v)
    380 		return par[v] = top(par[v]);
    381 	return v;
    382 }
    383 
    384 bool unite(int u, int v) {
    385 	u = top(u);
    386 	v = top(v);
    387 	if (u == v)
    388 		return false;
    389 	if (rk[u] < rk[v])
    390 		swap(u, v);
    391 	par[v] = u;
    392 	rk[u] += rk[v];
    393 	return true;
    394 }
    395 
    396 vector<int> F;
    397 void inc(int pos, int val) {
    398 	for(; pos < sz(F); pos |= pos + 1)
    399 		F[pos] += val;
    400 }
    401 int sum(int pos) {
    402 	int ans = 0;
    403 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    404 		ans += F[pos];
    405 	return ans;
    406 }
    407 
    408 void addOnPath(int v, int l) {
    409 	while (v != l) {
    410 		inc(tin[v], 1);
    411 		inc(tout[v], -1);
    412 		v = up[0][v];
    413 	}
    414 }
    415 
    416 inline void solve() {
    417 	init(n);
    418 	g.resize(n);
    419 	
    420 	vector<int> ans(q, -1);
    421 	fore (i, 0, q) {
    422 		int u = es[i][0];
    423 		int v = es[i][1];
    424 		int x = es[i][2];
    425 		
    426 		if (unite(u, v)) {
    427 			ans[i] = 1;
    428 			g[u].emplace_back(v, x);
    429 			g[v].emplace_back(u, x);
    430 		}
    431 	}
    432 	
    433 	buildLCA();
    434 	F.assign(2 * n + 5, 0);
    435 	
    436 	fore (i, 0, q) {
    437 		if (ans[i] != -1)
    438 			continue;
    439 		
    440 		ans[i] = 0;
    441 		int u = es[i][0];
    442 		int v = es[i][1];
    443 		int x = es[i][2];
    444 		
    445 		int xorPath = xr[u] ^ xr[v];
    446 		if ((xorPath ^ x) != 1)
    447 			continue;
    448 		
    449 		int l = lca(u, v);
    450 		int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
    451 		if (usedOnPath > 0)
    452 			continue;
    453 		
    454 		ans[i] = 1;
    455 		addOnPath(u, l);
    456 		addOnPath(v, l);
    457 	}
    458 	
    459 	for (int res : ans)
    460 		cout << (res ? "YES" : "NO") << '\n';
    461 }
    462 
    463 int main() {
    464 #ifdef _DEBUG
    465 	freopen("input.txt", "r", stdin);
    466 	int tt = clock();
    467 #endif
    468 	ios_base::sync_with_stdio(false);
    469 	cin.tie(0), cout.tie(0);
    470 	cout << fixed << setprecision(15);
    471 	
    472 	if(read()) {
    473 		solve();
    474 		
    475 #ifdef _DEBUG
    476 		cerr << "TIME = " << clock() - tt << endl;
    477 		tt = clock();
    478 #endif
    479 	}
    480 	return 0;
    481 }
    482 ```