codeforces-scrape

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

1633.md (10356B)


      1 Source: https://codeforces.com/blog/entry/99539
      2 
      3 [1633A - Div. 7](/contest/1633/problem/A "Educational Codeforces Round 122 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [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     if n % 7 == 0:
     18         print(n)
     19     else:
     20         ans = -1
     21         for j in range(10):
     22             if (n - n % 10 + j) % 7 == 0:
     23                 ans = n - n % 10 + j
     24         print(ans)
     25 ```
     26 
     27 [1633B - Minority](/contest/1633/problem/B "Educational Codeforces Round 122 (Rated for Div. 2)")
     28 
     29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") and [Neon](/profile/Neon "Candidate Master Neon")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution (awoo)**
     36 
     37 ```
     38 for _ in range(int(input())):
     39     s = input()
     40     print(min((len(s) - 1) // 2, s.count('0'), s.count('1')))
     41 ```
     42 
     43 [1633C - Kill the Monster](/contest/1633/problem/C "Educational Codeforces Round 122 (Rated for Div. 2)")
     44 
     45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (awoo)**
     52 
     53 ```
     54 for _ in range(int(input())):
     55     hc, dc = map(int, input().split())
     56     hm, dm = map(int, input().split())
     57     k, w, a = map(int, input().split())
     58     for i in range(k + 1):
     59         nhc = hc + i * a
     60         ndc = dc + (k - i) * w
     61         if (hm + ndc - 1) // ndc <= (nhc + dm - 1) // dm:
     62             print("YES")
     63             break
     64     else:
     65         print("NO")
     66 ```
     67 
     68 [1633D - Make Them Equal](/contest/1633/problem/D "Educational Codeforces Round 122 (Rated for Div. 2)")
     69 
     70 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     71 
     72 **Tutorial**
     73 
     74 Tutorial is loading...
     75 
     76 **Solution (Neon)**
     77 
     78 ```
     79 #include <bits/stdc++.h>
     80 
     81 using namespace std;
     82 
     83 const int N = 1001;
     84 
     85 int main() {
     86   vector<int> d(N, N);
     87   d[1] = 0;
     88   for (int i = 1; i < N; ++i) {
     89     for (int x = 1; x <= i; ++x) {
     90       int j = i + i / x;
     91       if (j < N) d[j] = min(d[j], d[i] + 1);
     92     }
     93   }
     94   
     95   int t;
     96   cin >> t;
     97   while (t--) {
     98     int n, k;
     99     cin >> n >> k;
    100     vector<int> b(n), c(n);
    101     for (int &x : b) cin >> x;
    102     for (int &x : c) cin >> x;
    103     int sum = 0;
    104     for (int x : b) sum += d[x];
    105     k = min(k, sum);
    106     vector<int> dp(k + 1, 0);
    107     for (int i = 0; i < n; ++i) {
    108       for (int j = k - d[b[i]]; j >= 0; j--) {
    109         dp[j + d[b[i]]] = max(dp[j + d[b[i]]], dp[j] + c[i]);
    110       }
    111     }
    112     cout << *max_element(dp.begin(), dp.end()) << '\n';
    113   }
    114 }
    115 ```
    116 
    117 [1633E - Spanning Tree Queries](/contest/1633/problem/E "Educational Codeforces Round 122 (Rated for Div. 2)")
    118 
    119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution (awoo)**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 
    130 #define forn(i, n) for (int i = 0; i < int(n); i++)
    131 
    132 using namespace std;
    133 
    134 struct edge{
    135 	int v, u, w;
    136 };
    137 
    138 vector<int> pr, rk;
    139 
    140 int getp(int a){
    141 	return a == pr[a] ? a : pr[a] = getp(pr[a]);
    142 }
    143 
    144 bool unite(int a, int b){
    145 	a = getp(a), b = getp(b);
    146 	if (a == b) return false;
    147 	if (rk[a] < rk[b]) swap(a, b);
    148 	rk[a] += rk[b];
    149 	pr[b] = a;
    150 	return true;
    151 }
    152 
    153 int main() {
    154 	int n, m;
    155 	scanf("%d%d", &n, &m);
    156 	pr.resize(n);
    157 	rk.resize(n);
    158 	vector<edge> es(m);
    159 	forn(i, m){
    160 		scanf("%d%d%d", &es[i].v, &es[i].u, &es[i].w);
    161 		--es[i].v, --es[i].u;
    162 		es[i].w *= 2;
    163 	}
    164 	vector<int> ev(1, 0);
    165 	forn(i, m) forn(j, i + 1) ev.push_back((es[i].w + es[j].w) / 2);
    166 	sort(ev.begin(), ev.end());
    167 	ev.resize(unique(ev.begin(), ev.end()) - ev.begin());
    168 	vector<long long> base;
    169 	vector<int> cnt;
    170 	for (int x : ev){
    171 		sort(es.begin(), es.end(), [&x](const edge &a, const edge &b){
    172 			int wa = abs(a.w - x);
    173 			int wb = abs(b.w - x);
    174 			if (wa != wb) return wa < wb;
    175 			return a.w > b.w;
    176 		});
    177 		forn(i, n) pr[i] = i, rk[i] = 1;
    178 		long long cur_base = 0;
    179 		int cur_cnt = 0;
    180 		for (const auto &e : es) if (unite(e.v, e.u)){
    181 			cur_base += abs(e.w - x);
    182 			cur_cnt += x < e.w;
    183 		}
    184 		base.push_back(cur_base);
    185 		cnt.push_back(cur_cnt);
    186 	}
    187 	int p, k, a, b, c;
    188 	scanf("%d%d%d%d%d", &p, &k, &a, &b, &c);
    189 	int x = 0;
    190 	long long ans = 0;
    191 	forn(q, k){
    192 		if (q < p) scanf("%d", &x);
    193 		else x = (x * 1ll * a + b) % c;
    194 		int y = upper_bound(ev.begin(), ev.end(), 2 * x) - ev.begin() - 1;
    195 		ans ^= (base[y] + (n - 1 - 2 * cnt[y]) * 1ll * (2 * x - ev[y])) / 2;
    196 	}
    197 	printf("%lld\n", ans);
    198 	return 0;
    199 }
    200 ```
    201 
    202 [1633F - Perfect Matching](/contest/1633/problem/F "Educational Codeforces Round 122 (Rated for Div. 2)")
    203 
    204 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    205 
    206 **Tutorial**
    207 
    208 Tutorial is loading...
    209 
    210 **Solution (BledDest)**
    211 
    212 ```
    213 #include <bits/stdc++.h>     
    214 
    215 using namespace std;
    216 
    217 typedef pair<long long, int> val;
    218 
    219 #define x first 
    220 #define y second
    221 
    222 const int N = 200043;
    223 
    224 val operator +(const val& a, const val& b)
    225 {
    226     return make_pair(a.x + b.x, a.y + b.y);
    227 }
    228 
    229 val operator -(const val& a, const val& b)
    230 {
    231     return make_pair(a.x - b.x, a.y - b.y);
    232 }
    233 
    234 val T[4 * N];
    235 val Tfull[4 * N];
    236 int f[4 * N];
    237 
    238 val getVal(int v)
    239 {
    240     if(f[v] == 1)
    241         return Tfull[v] - T[v];
    242     return T[v];
    243 }
    244 
    245 void push(int v)
    246 {
    247     if(f[v] == 1)
    248     {
    249         f[v] = 0;
    250         T[v] = Tfull[v] - T[v];
    251         f[v * 2 + 1] ^= 1;
    252         f[v * 2 + 2] ^= 1;
    253     }   
    254 }                
    255 
    256 void upd(int v)
    257 {
    258     Tfull[v] = Tfull[v * 2 + 1] + Tfull[v * 2 + 2];
    259     T[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);
    260 }
    261 
    262 void setVal(int v, int l, int r, int pos, val cur)
    263 {                                                           
    264     if(l == r - 1)
    265     {
    266         f[v] = 0;
    267         Tfull[v] = cur;
    268         T[v] = cur;
    269     }
    270     else
    271     {
    272         push(v);
    273         int m = (l + r) / 2;
    274         if(pos < m)
    275             setVal(v * 2 + 1, l, m, pos, cur);
    276         else
    277             setVal(v * 2 + 2, m, r, pos, cur);
    278         upd(v);
    279     }
    280 }
    281 
    282 void flipColor(int v, int l, int r, int L, int R)
    283 {
    284     if(L >= R) return;
    285     if(l == L && r == R)
    286         f[v] ^= 1;
    287     else
    288     {
    289         push(v);
    290         int m = (l + r) / 2;
    291         flipColor(v * 2 + 1, l, m, L, min(m, R));
    292         flipColor(v * 2 + 2, m, r, max(L, m), R);
    293         upd(v);
    294     }
    295 }
    296 
    297 val getVal(int v, int l, int r, int L, int R)
    298 {
    299     if(L >= R) return make_pair(0ll, 0);
    300     if(l == L && r == R) return getVal(v);
    301     int m = (l + r) / 2;
    302     val ans = make_pair(0ll, 0);
    303     push(v);
    304     ans = ans + getVal(v * 2 + 1, l, m, L, min(R, m));
    305     ans = ans + getVal(v * 2 + 2, m, r, max(L, m), R);
    306     upd(v);
    307     return ans;
    308 }
    309 
    310 int n;
    311 vector<int> g[N];
    312 
    313 int p[N], siz[N], d[N], nxt[N];
    314 int tin[N], timer;
    315 map<pair<int, int>, int> idx;
    316 long long sum;
    317 int cnt;
    318 int active[N];
    319 int active_cnt;
    320 
    321 void dfs_sz(int v) 
    322 {
    323     if (p[v] != -1) 
    324     {
    325         auto it = find(g[v].begin(), g[v].end(), p[v]);
    326         if (it != g[v].end())
    327             g[v].erase(it);
    328     }
    329     siz[v] = 1;
    330     for (int &u : g[v]) 
    331     {
    332         p[u] = v;
    333         d[u] = d[v] + 1;
    334         dfs_sz(u);
    335         siz[v] += siz[u];
    336         if (siz[u] > siz[g[v][0]])
    337             swap(u, g[v][0]);
    338     }
    339 }
    340 
    341 void dfs_hld(int v) 
    342 {
    343     tin[v] = timer++;
    344     for (int u : g[v]) 
    345     {
    346         nxt[u] = (u == g[v][0] ? nxt[v] : u);
    347         dfs_hld(u);
    348     }
    349 }
    350 
    351 // [l; r] inclusive
    352 void flipSegment(int l, int r) 
    353 {
    354     flipColor(0, 0, n, l, r + 1);        
    355 }
    356 
    357 // [l; r] inclusive
    358 val get(int l, int r) 
    359 {
    360     return getVal(0, 0, n, l, r + 1);   
    361 }
    362 
    363 void flipPath(int v, int u) 
    364 {
    365     for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 
    366     {
    367         if (d[nxt[v]] > d[nxt[u]]) swap(v, u);
    368         flipSegment(tin[nxt[u]], tin[u]);
    369     }
    370     if (d[v] > d[u]) swap(v, u);
    371     flipSegment(tin[v], tin[u]);
    372 }
    373 
    374 val getPath(int v, int u) 
    375 {
    376     val res = make_pair(0ll, 0);
    377     for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 
    378     {
    379         if (d[nxt[v]] > d[nxt[u]]) swap(v, u);
    380         // update res with the result of get()
    381         res = res + get(tin[nxt[u]], tin[u]);
    382     }
    383     if (d[v] > d[u]) swap(v, u);
    384     res = res + get(tin[v], tin[u]);
    385     return res;
    386 }
    387 
    388 void activate_vertex(int x)
    389 {
    390     int id = 0;
    391     if(p[x] != -1)
    392     {                       
    393         id = idx[make_pair(x, p[x])];
    394         val v = getPath(0, p[x]);
    395         flipPath(0, p[x]);
    396         sum -= v.x;
    397         cnt -= v.y;
    398         v = getPath(0, p[x]);
    399         sum += v.x;
    400         cnt += v.y;
    401     }                   
    402     cnt++;
    403     sum += id;
    404     setVal(0, 0, n, tin[x], make_pair((long long)(id), 1));
    405     active[x] = 1;
    406     active_cnt++;   
    407 }          
    408 
    409 void init_hld(int root = 0) 
    410 {
    411     d[root] = 0;
    412     nxt[root] = root;
    413     p[root] = -1;
    414     timer = 0;
    415     dfs_sz(root);
    416     dfs_hld(root);
    417 }
    418 
    419 int currentSize[N];
    420 
    421 int dfsSolution(int x, vector<int>& edges)
    422 {
    423     if(!active[x]) return 0;
    424     currentSize[x] = 1;
    425     for(auto y : g[x])
    426         if(y != p[x])
    427             currentSize[x] += dfsSolution(y, edges);
    428     if(currentSize[x] % 2 == 1)
    429         edges.push_back(idx[make_pair(x, p[x])]);
    430     return currentSize[x];   
    431 }
    432 
    433 void outputSolution()
    434 {
    435     vector<int> edges;
    436     if(cnt * 2 == active_cnt)
    437     {
    438         dfsSolution(0, edges);
    439         sort(edges.begin(), edges.end());
    440     }
    441     printf("%d", int(edges.size()));
    442     for(auto x : edges) printf(" %d", x);
    443     puts("");
    444     fflush(stdout);
    445 }
    446 
    447 void processQuery(int v)
    448 {
    449     activate_vertex(v);
    450     if(cnt * 2 == active_cnt)
    451         printf("%lld\n", sum);
    452     else
    453         puts("0");
    454     fflush(stdout);
    455 }
    456 
    457 int main()
    458 {
    459     scanf("%d", &n);
    460     for(int i = 1; i < n; i++)
    461     {
    462         int x, y;
    463         scanf("%d %d", &x, &y);
    464         --x;
    465         --y;
    466         g[x].push_back(y);
    467         g[y].push_back(x);
    468         idx[make_pair(x, y)] = i;
    469         idx[make_pair(y, x)] = i;
    470     }   
    471     
    472     init_hld();         
    473     activate_vertex(0); 
    474     while(true)
    475     {
    476         int t;
    477         scanf("%d", &t);       
    478         if(t == 3)
    479             break;
    480         if(t == 2)
    481             outputSolution();
    482         if(t == 1)
    483         {
    484             int v;          
    485             scanf("%d", &v);
    486             --v;
    487             processQuery(v);
    488         } 
    489     }
    490 }
    491 ```