codeforces-scrape

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

1681.md (8926B)


      1 Source: https://codeforces.com/blog/entry/103163
      2 
      3 [1681A - Game with Cards](/contest/1681/problem/A "Educational Codeforces Round 129 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     a = list(map(int, input().split()))
     18     m = int(input())
     19     b = list(map(int, input().split()))
     20     
     21     print('Alice' if max(a) >= max(b) else 'Bob')
     22     print('Alice' if max(a) > max(b) else 'Bob')
     23 ```
     24 
     25 [1681B - Card Trick](/contest/1681/problem/B "Educational Codeforces Round 129 (Rated for Div. 2)")
     26 
     27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution (awoo)**
     34 
     35 ```
     36 for _ in range(int(input())):
     37 	n = int(input())
     38 	a = list(map(int, input().split()))
     39 	m = int(input())
     40 	print(a[sum(map(int, input().split())) % n])
     41 ```
     42 
     43 [1681C - Double Sort](/contest/1681/problem/C "Educational Codeforces Round 129 (Rated for Div. 2)")
     44 
     45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (awoo)**
     52 
     53 ```
     54 for _ in range(int(input())):
     55 	n = int(input())
     56 	a = list(map(int, input().split()))
     57 	b = list(map(int, input().split()))
     58 	tmp = [i for i in range(n)]
     59 	tmp.sort(key=lambda i: [a[i], b[i]])
     60 	for i in range(n - 1):
     61 		if a[tmp[i]] > a[tmp[i + 1]] or b[tmp[i]] > b[tmp[i + 1]]:
     62 			print("-1")
     63 			break
     64 	else:
     65 		ans = []
     66 		for i in range(n - 1):
     67 			for j in range(n - 1):
     68 				if a[j] > a[j + 1] or b[j] > b[j + 1]:
     69 					a[j], a[j + 1] = a[j + 1], a[j]
     70 					b[j], b[j + 1] = b[j + 1], b[j]
     71 					ans.append([j + 1, j + 2])
     72 		print(len(ans))
     73 		for it in ans:
     74 			print(*it)
     75 ```
     76 
     77 [1681D - Required Length](/contest/1681/problem/D "Educational Codeforces Round 129 (Rated for Div. 2)")
     78 
     79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution (BledDest)**
     86 
     87 ```
     88 #include<bits/stdc++.h>
     89 
     90 using namespace std;
     91 
     92 int main()
     93 {   
     94     int n;
     95     cin >> n;
     96     long long v;
     97     cin >> v;
     98     queue<long long> q;
     99     map<long long, int> dist;
    100     dist[v] = 0;
    101     q.push(v);
    102     while(!q.empty())
    103     {
    104         long long k = q.front();
    105         q.pop();
    106         string s = to_string(k);
    107         if(s.size() == n)
    108         {
    109             cout << dist[k] << endl;
    110             return 0;
    111         }
    112         for(auto x : s)
    113         {
    114             if(x == '0') continue;
    115             long long w = k * int(x - '0');
    116             if(!dist.count(w))
    117             {
    118                 dist[w] = dist[k] + 1;
    119                 q.push(w);
    120             }
    121         }
    122     }
    123     cout << -1 << endl;
    124     return 0;
    125 }
    126 ```
    127 
    128 [1681E - Labyrinth Adventures](/contest/1681/problem/E "Educational Codeforces Round 129 (Rated for Div. 2)")
    129 
    130 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    131 
    132 **Tutorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Solution (awoo)**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 
    141 #define forn(i, n) for (int i = 0; i < int(n); i++)
    142 
    143 using namespace std;
    144 
    145 const long long INF64 = 1e18;
    146 
    147 typedef pair<int, int> pt;
    148 #define x first
    149 #define y second
    150 
    151 int main() {
    152 	int n;
    153 	scanf("%d", &n);
    154 	vector<vector<pt>> d(n - 1, vector<pt>(2));
    155 	forn(i, n - 1) forn(j, 2){
    156 		scanf("%d%d", &d[i][j].x, &d[i][j].y);
    157 		--d[i][j].x, --d[i][j].y;
    158 	}
    159 	int lg = 1;
    160 	while ((1 << lg) < n - 1) ++lg;
    161 	vector<vector<vector<vector<long long>>>> dp(n - 2, vector<vector<vector<long long>>>(lg, vector<vector<long long>>(2, vector<long long>(2, INF64))));
    162 	forn(i, n - 2) forn(k, 2){
    163 		dp[i][0][0][k] = abs(d[i][0].x + 1 - d[i + 1][k].x) + abs(d[i][0].y - d[i + 1][k].y) + 1;
    164 		dp[i][0][1][k] = abs(d[i][1].x - d[i + 1][k].x) + abs(d[i][1].y + 1 - d[i + 1][k].y) + 1;
    165 	}
    166 	for (int l = 1; l < lg; ++l) forn(i, n - 2) forn(j, 2) forn(k, 2) forn(t, 2) if (i + (1 << (l - 1)) < n - 2){
    167 		dp[i][l][j][k] = min(dp[i][l][j][k], dp[i][l - 1][j][t] + dp[i + (1 << (l - 1))][l - 1][t][k]);
    168 	}
    169 	int m;
    170 	scanf("%d", &m);
    171 	forn(_, m){
    172 		int x1, y1, x2, y2;
    173 		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    174 		--x1, --y1, --x2, --y2;
    175 		int l1 = max(x1, y1), l2 = max(x2, y2);
    176 		if (l1 > l2){
    177 			swap(l1, l2);
    178 			swap(x1, x2);
    179 			swap(y1, y2);
    180 		}
    181 		if (l1 == l2){
    182 			printf("%d\n", abs(x1 - x2) + abs(y1 - y2));
    183 			continue;
    184 		}
    185 		vector<long long> ndp(2);
    186 		ndp[0] = abs(x1 - d[l1][0].x) + abs(y1 - d[l1][0].y);
    187 		ndp[1] = abs(x1 - d[l1][1].x) + abs(y1 - d[l1][1].y);
    188 		for (int i = lg - 1; i >= 0; --i) if (l1 + (1 << i) < l2){
    189 			vector<long long> tmp(2, INF64);
    190 			forn(j, 2) forn(k, 2)
    191 				tmp[k] = min(tmp[k], ndp[j] + dp[l1][i][j][k]);
    192 			ndp = tmp;
    193 			l1 += (1 << i);
    194 		}
    195 		long long ans = INF64;
    196 		ans = min(ans, ndp[0] + abs(d[l1][0].x + 1 - x2) + abs(d[l1][0].y - y2) + 1);
    197 		ans = min(ans, ndp[1] + abs(d[l1][1].x - x2) + abs(d[l1][1].y + 1 - y2) + 1);
    198 		printf("%lld\n", ans);
    199 	}
    200 	return 0;
    201 }
    202 ```
    203 
    204 [1681F - Unique Occurrences](/contest/1681/problem/F "Educational Codeforces Round 129 (Rated for Div. 2)")
    205 
    206 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution 1 (awoo)**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 
    217 #define forn(i, n) for (int i = 0; i < int(n); i++)
    218 
    219 using namespace std;
    220 
    221 struct edge{
    222 	int u, w;
    223 };
    224 
    225 int n;
    226 vector<vector<edge>> g;
    227 vector<vector<int>> ng;
    228 vector<int> tin, tout, siz, ord;
    229 int T;
    230 
    231 vector<int> pw;
    232 
    233 void init(int v, int p = -1){
    234 	tin[v] = T++;
    235 	ord.push_back(v);
    236 	siz[v] = 1;
    237 	for (const auto &it : g[v]){
    238 		int u = it.u, w = it.w;
    239 		if (u == p) continue;
    240 		pw[u] = w;
    241 		init(u, v);
    242 		siz[v] += siz[u];
    243 	}
    244 	tout[v] = T;
    245 }
    246 
    247 int isp(int v, int u){
    248 	return tin[v] <= tin[u] && tout[v] >= tout[u];
    249 }
    250 
    251 vector<int> nsiz;
    252 vector<vector<int>> dp;
    253 
    254 long long dfs(int v, int x){
    255 	long long res = 0;
    256 	for (int u : ng[v])
    257 		res += dfs(u, x);
    258 	dp[v][0] = siz[v];
    259 	dp[v][1] = 0;
    260 	for (int u : ng[v]) dp[v][0] -= siz[u];
    261 	for (int u : ng[v]){
    262 		if (pw[u] == x){
    263 			res += dp[u][0] * 1ll * dp[v][0];
    264 			dp[v][1] += dp[u][0];
    265 		}
    266 		else{
    267 			res += dp[u][0] * 1ll * dp[v][1];
    268 			res += dp[u][1] * 1ll * dp[v][0];
    269 			dp[v][0] += dp[u][0];
    270 			dp[v][1] += dp[u][1];
    271 		}
    272 	}
    273 	return res;
    274 }
    275 
    276 int main() {
    277 	scanf("%d", &n);
    278 	
    279 	g.resize(n);
    280 	forn(i, n - 1){
    281 		int v, u, w;
    282 		scanf("%d%d%d", &v, &u, &w);
    283 		--v, --u, --w;
    284 		g[v].push_back({u, w});
    285 		g[u].push_back({v, w});
    286 	}
    287 	
    288 	T = 0;
    289 	tin.resize(n);
    290 	tout.resize(n);
    291 	siz.resize(n);
    292 	pw.resize(n, -1);
    293 	init(0);
    294 	
    295 	vector<vector<int>> sv(n, vector<int>(1, 0));
    296 	for (int v : ord) for (auto it : g[v])
    297 		sv[it.w].push_back(v);
    298 	
    299 	ng.resize(n);
    300 	nsiz.resize(n);
    301 	dp.resize(n, vector<int>(2));
    302 	long long ans = 0;
    303 	forn(i, n) if (!sv[i].empty()){
    304 		sv[i].resize(unique(sv[i].begin(), sv[i].end()) - sv[i].begin());
    305 		vector<int> st;
    306 		for (int v : sv[i]){
    307 			while (!st.empty() && !isp(st.back(), v))
    308 				st.pop_back();
    309 			if (!st.empty())
    310 				ng[st.back()].push_back(v);
    311 			st.push_back(v);
    312 		}
    313 		ans += dfs(0, i);
    314 		
    315 		for (int v : sv[i]) ng[v].clear();
    316 	}
    317 	
    318 	printf("%lld\n", ans);
    319 	return 0;
    320 }
    321 ```
    322 
    323 **Solution 2 (awoo)**
    324 
    325 ```
    326 #include <bits/stdc++.h>
    327 
    328 #define forn(i, n) for (int i = 0; i < int(n); i++)
    329 
    330 using namespace std;
    331 
    332 struct edge{
    333 	int v, u, w;
    334 };
    335 
    336 vector<vector<edge>> t;
    337 
    338 void add(int v, int l, int r, int L, int R, const edge &e){
    339 	if (L >= R)
    340 		return;
    341 	if (l == L && r == R){
    342 		t[v].push_back(e);
    343 		return;
    344 	}
    345 	int m = (l + r) / 2;
    346 	add(v * 2, l, m, L, min(m, R), e);
    347 	add(v * 2 + 1, m, r, max(m, L), R, e);
    348 }
    349 
    350 vector<int> rk, p;
    351 vector<int*> where;
    352 vector<int> val;
    353 
    354 int getp(int a){
    355 	return a == p[a] ? a : getp(p[a]);
    356 }
    357 
    358 void unite(int a, int b){
    359 	a = getp(a), b = getp(b);
    360 	if (a == b) return;
    361 	if (rk[a] < rk[b]) swap(a, b);
    362 	where.push_back(&rk[a]);
    363 	val.push_back(rk[a]);
    364 	rk[a] += rk[b];
    365 	where.push_back(&p[b]);
    366 	val.push_back(p[b]);
    367 	p[b] = a;
    368 }
    369 
    370 void rollback(){
    371 	*where.back() = val.back();
    372 	where.pop_back();
    373 	val.pop_back();
    374 }
    375 
    376 long long trav(int v, int l, int r){
    377 	int sv = where.size();
    378 	for (auto it : t[v]) if (it.w == 0)
    379 		unite(it.v, it.u);
    380 	long long res = 0;
    381 	if (l == r - 1){
    382 		for (auto it : t[v]) if (it.w == 1)
    383 			res += rk[getp(it.v)] * 1ll * rk[getp(it.u)];
    384 	}
    385 	else{
    386 		int m = (l + r) / 2;
    387 		res += trav(v * 2, l, m);
    388 		res += trav(v * 2 + 1, m, r);
    389 	}
    390 	while (int(where.size()) > sv) rollback();
    391 	return res;
    392 }
    393 
    394 int main() {
    395 	int n;
    396 	scanf("%d", &n);
    397 	vector<edge> e(n - 1);
    398 	forn(i, n - 1){
    399 		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
    400 		--e[i].v, --e[i].u, --e[i].w;
    401 	}
    402 	sort(e.begin(), e.end(), [](const edge &a, const edge &b){
    403 		return a.w < b.w;
    404 	});
    405 	t.resize(4 * n);
    406 	forn(i, n - 1){
    407 		int pos = lower_bound(e.begin(), e.end(), e[i], [](const edge &a, const edge &b){
    408 			return a.w < b.w;
    409 		}) - e.begin();
    410 		add(1, 0, n, 0, pos, {e[i].v, e[i].u, 0});
    411 		add(1, 0, n, pos, pos + 1, {e[i].v, e[i].u, 1});
    412 		add(1, 0, n, pos + 1, n, {e[i].v, e[i].u, 0});
    413 	}
    414 	rk.resize(n, 1);
    415 	p.resize(n);
    416 	iota(p.begin(), p.end(), 0);
    417 	printf("%lld\n", trav(1, 0, n));
    418 	return 0;
    419 }
    420 ```