codeforces-scrape

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

1767.md (10073B)


      1 Source: https://codeforces.com/blog/entry/110225
      2 
      3 [1767A - Cut the Triangle](/contest/1767/problem/A "Educational Codeforces Round 140 (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     input()
     17     xs = []
     18     ys = []
     19     for j in range(3):
     20         x, y = map(int, input().split())
     21         xs.append(x)
     22         ys.append(y)
     23     print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO')
     24 ```
     25 
     26 [1767B - Block Towers](/contest/1767/problem/B "Educational Codeforces Round 140 (Rated for Div. 2)")
     27 
     28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (awoo)**
     35 
     36 ```
     37 for _ in range(int(input())):
     38     n = int(input())
     39     a = list(map(int, input().split()))
     40     x = a[0]
     41     a = sorted(a[1:])
     42     for y in a:
     43         if y > x:
     44             x += (y - x + 1) // 2
     45     print(x)
     46 ```
     47 
     48 [1767C - Count Binary Strings](/contest/1767/problem/C "Educational Codeforces Round 140 (Rated for Div. 2)")
     49 
     50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Solution (BledDest)**
     57 
     58 ```
     59 #include<bits/stdc++.h>
     60 
     61 using namespace std;
     62 
     63 const int MOD = 998244353;
     64 
     65 int add(int x, int y)
     66 {
     67     x += y;
     68     while(x >= MOD) x -= MOD;
     69     while(x < 0) x += MOD;
     70     return x;
     71 }
     72 
     73 int mul(int x, int y)
     74 {
     75     return (x * 1ll * y) % MOD;
     76 }
     77 
     78 const int N = 143;
     79 int n;
     80 
     81 int a[N][N];
     82 int dp[N][N];
     83 
     84 bool check(int cnt, int last)
     85 {
     86     for(int i = 0; i < cnt; i++)
     87     {
     88         if(a[i][cnt - 1] == 0) continue;
     89         if(a[i][cnt - 1] == 1 && last > i) return false;
     90         if(a[i][cnt - 1] == 2 && last <= i) return false;
     91     }
     92     return true;
     93 }
     94 
     95 int main()
     96 {
     97     cin >> n;
     98     for(int i = 0; i < n; i++)
     99     {
    100         for(int j = i; j < n; j++)
    101             cin >> a[i][j];
    102     }
    103     if(a[0][0] != 2) dp[1][0] = 2;
    104     for(int i = 1; i < n; i++)
    105         for(int j = 0; j < i; j++)
    106             for(int k : vector<int>({j, i}))
    107                 if(check(i + 1, k))
    108                     dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]);
    109     int ans = 0;
    110     for(int i = 0; i < n; i++)
    111         ans = add(ans, dp[n][i]);
    112     cout << ans << endl;
    113 }
    114 ```
    115 
    116 [1767D - Playoff](/contest/1767/problem/D "Educational Codeforces Round 140 (Rated for Div. 2)")
    117 
    118 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution (Neon)**
    125 
    126 ```
    127 #include <bits/stdc++.h>
    128 
    129 using namespace std;
    130 
    131 int main() {
    132   int n;
    133   string s;
    134   cin >> n >> s;
    135   int k = count(s.begin(), s.end(), '1');
    136   for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x)
    137     cout << x << ' ';
    138 }
    139 ```
    140 
    141 [1767E - Algebra Flash](/contest/1767/problem/E "Educational Codeforces Round 140 (Rated for Div. 2)")
    142 
    143 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution (awoo)**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153 
    154 #define forn(i, n) for (int i = 0; i < int(n); i++)
    155 
    156 using namespace std;
    157 
    158 int main() {
    159     int n, m;
    160     scanf("%d%d", &n, &m);
    161     vector<int> c(n);
    162     forn(i, n){
    163         scanf("%d", &c[i]);
    164         --c[i];
    165     }
    166     vector<int> x(m);
    167     forn(i, m) scanf("%d", &x[i]);
    168     
    169     vector<long long> g(m);
    170     forn(i, n - 1){
    171         g[c[i]] |= 1ll << c[i + 1];
    172         g[c[i + 1]] |= 1ll << c[i];
    173     }
    174     g[c[0]] |= 1ll << c[0];
    175     g[c[n - 1]] |= 1ll << c[n - 1];
    176     
    177     int mid = m / 2;
    178     vector<int> dp(1 << mid, 1e9);
    179     forn(mask, 1 << (m - mid)){
    180         long long chk = 0;
    181         int tot = 0;
    182         forn(i, m - mid){
    183             if ((mask >> i) & 1)
    184                 tot += x[i + mid];
    185             else
    186                 chk |= g[i + mid];
    187         }
    188         if (((chk >> mid) | mask) != mask)
    189             continue;
    190         chk &= (1ll << mid) - 1;
    191         dp[chk] = min(dp[chk], tot);
    192     }
    193     forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){
    194         dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]);
    195     }
    196     int ans = 1e9;
    197     forn(mask, 1 << mid){
    198         long long chk = 0;
    199         int tot = 0;
    200         forn(i, mid){
    201             if ((mask >> i) & 1)
    202                 tot += x[i];
    203             else
    204                 chk |= g[i];
    205         }
    206         chk &= (1ll << mid) - 1;
    207         if ((chk | mask) != mask)
    208             continue;
    209         ans = min(ans, dp[mask] + tot);
    210     }
    211     printf("%d\n", ans);
    212     return 0;
    213 }
    214 ```
    215 
    216 [1767F - Two Subtrees](/contest/1767/problem/F "Educational Codeforces Round 140 (Rated for Div. 2)")
    217 
    218 Idea: [shnirelman](/profile/shnirelman "Grandmaster shnirelman")
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution (shnirelman)**
    225 
    226 ```
    227 #include <bits/stdc++.h>
    228 
    229 #define f first
    230 #define s second
    231 
    232 using namespace std;
    233 using li = long long;
    234 using ld = long double;
    235 using pii = pair<int, int>;
    236 
    237 const int INF = 2e9 + 13;
    238 const li INF64 = 2e18 + 13;
    239 const int M = 998244353;
    240 const int A = 2e5 + 13;
    241 
    242 const int N = 2e5 + 13;
    243 const int B = 2000;
    244 const int SQRTA = 500;
    245 const int K = N / B + 113;
    246 
    247 int val[N];
    248 vector<int> g[N];
    249 int sz[N];
    250 int gr[N];
    251 int leaf[N], group_root[N];
    252 int par[N];
    253 bool heavy[N];
    254 
    255 int tin[N], tout[N], T = 0, mid[N];
    256 int et[N];
    257 int valet[N];
    258 
    259 void dfs1(int v, int pr, int depth) {
    260     par[v] = pr;
    261     sz[v] = 1;
    262 
    263     int mx = -1;
    264     for(int i = 0; i < g[v].size(); i++) {
    265         int u = g[v][i];
    266         if(u != pr) {
    267             dfs1(u, v, depth + 1);
    268             sz[v] += sz[u];
    269             if(mx == -1 || sz[g[v][mx]] < sz[u])
    270                 mx = i;
    271         }
    272     }
    273 
    274     if(mx != -1)
    275         swap(g[v][mx], g[v][0]);
    276 }
    277 
    278 void dfs2(int v) {
    279     et[T] = v;
    280     tin[v] = T++;
    281 
    282     for(int u : g[v]) {
    283         if(u != par[v])
    284             dfs2(u);
    285     }
    286 
    287     tout[v] = T;
    288 }
    289 
    290 struct Query {
    291     int ind;
    292     int v, u;
    293     int lv, rv, lu, ru;
    294     int b;
    295 
    296     Query() {};
    297 };
    298 
    299 bool cmp(const Query& a, const Query& b) {
    300     if(a.b != b.b)
    301         return a.b < b.b;
    302     else
    303         return a.lu < b.lu;
    304 }
    305 
    306 int cnt[A];
    307 int block_index[A];
    308 int block_mx[A];
    309 int block_cnt_of_cnt[A / SQRTA + 13][A];
    310 
    311 inline void insert(int i) {
    312     block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    313     cnt[valet[i]]++;
    314     block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
    315     if(cnt[valet[i]] > block_mx[block_index[valet[i]]])
    316         block_mx[block_index[valet[i]]]++;
    317 }
    318 
    319 inline void erase(int i) {
    320     if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1)
    321         block_mx[block_index[valet[i]]]--;
    322     block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    323     cnt[valet[i]]--;
    324     block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
    325 }
    326 
    327 int get_mode() {
    328     int mx = 0;
    329     for(int i = 0; i < A / SQRTA + 1; i++)
    330         mx = max(mx, block_mx[i]);
    331     for(int i = 0; ; i++) {
    332         if(block_mx[i] == mx) {
    333             for(int j = i * SQRTA; ; j++) {
    334                 if(cnt[j] == mx)
    335                     return j;
    336             }
    337         }
    338     }
    339 }
    340 
    341 Query queries[N];
    342 int ans[N];
    343 
    344 void solve() {
    345     int n;
    346     cin >> n;
    347 
    348     for(int i = 0; i < n; i++)
    349         cin >> val[i];
    350 
    351     for(int i = 1; i < n; i++) {
    352         int v, u;
    353         cin >> v >> u;
    354 
    355         v--;
    356         u--;
    357 
    358         g[v].push_back(u);
    359         g[u].push_back(v);
    360     }
    361 
    362     dfs1(0, -1, 0);
    363 
    364     vector<pii> ord(n);
    365     for(int i = 0; i < n; i++) {
    366         ord[i] = {sz[i], i};
    367         gr[i] = -1;
    368     }
    369 
    370     sort(ord.begin(), ord.end());
    371 
    372     for(int i = 0; i < n; i++) {
    373         if(sz[i] >= B)
    374             heavy[i] = true;
    375     }
    376 
    377     int cur = 0;
    378     for(int i = 0; i < n; i++) {
    379         int v = ord[i].s;
    380         if(sz[v] < B || gr[v] != -1)
    381             continue;
    382 
    383         leaf[cur] = v;
    384 
    385         int u = v;
    386         while(gr[u] == -1 && sz[u] - sz[v] < B) {
    387             gr[u] = cur;
    388             group_root[cur] = u;
    389             u = par[u];
    390         }
    391 
    392         cur++;
    393     }
    394 
    395     dfs2(0);
    396 
    397     for(int i = 0; i < n; i++) {
    398         if(sz[i] < B) {
    399             gr[i] = cur + tin[i] / B;
    400         }
    401     }
    402 
    403     for(int i = 0; i < n; i++)
    404         valet[i] = val[et[i]];
    405 
    406     for(int i = 0; i < A; i++) {
    407         block_index[i] = i / SQRTA;
    408     }
    409 
    410     int q;
    411     cin >> q;
    412 
    413     for(int i = 0; i < q; i++) {
    414         queries[i].ind = i;
    415         cin >> queries[i].v >> queries[i].u;
    416 
    417         queries[i].v--;
    418         queries[i].u--;
    419 
    420         queries[i].lv = tin[queries[i].v];
    421         queries[i].rv = tout[queries[i].v];
    422         queries[i].lu = tin[queries[i].u];
    423         queries[i].ru = tout[queries[i].u];
    424 
    425         if(queries[i].lv > queries[i].lu) {
    426             swap(queries[i].v, queries[i].u);
    427             swap(queries[i].lv, queries[i].lu);
    428             swap(queries[i].rv, queries[i].ru);
    429         }
    430 
    431         queries[i].b = gr[queries[i].v];
    432     }
    433 
    434     sort(queries, queries + q, cmp);
    435 
    436     int lv = 0, rv = 0, lu = 0, ru = 0;
    437     li fir = 0, sec = 0;
    438 
    439     int hs = 0;
    440     for(int i = 0; i < q; i++) {
    441         int qlv = queries[i].lv;
    442         int qrv = queries[i].rv;
    443         int qlu = queries[i].lu;
    444         int qru = queries[i].ru;
    445 
    446         fir += abs(lv - qlv) + abs(rv - qrv);
    447         sec += abs(lu - qlu) + abs(ru - qru);
    448 
    449         if(queries[i].b < cur) {
    450             while(rv < qrv)
    451                 insert(rv++);
    452             while(lv > qlv)
    453                 insert(--lv);
    454             while(rv > qrv)
    455                 erase(--rv);
    456             while(lv < qlv)
    457                 erase(lv++);
    458         } else {
    459             while(rv > lv)
    460                 erase(--rv);
    461             lv = qlv;
    462             rv = lv;
    463             while(rv < qrv)
    464                 insert(rv++);
    465         }
    466 
    467         while(ru < qru)
    468                 insert(ru++);
    469             while(lu > qlu)
    470                 insert(--lu);
    471             while(ru > qru)
    472                 erase(--ru);
    473             while(lu < qlu)
    474                 erase(lu++);
    475 
    476         ans[queries[i].ind] = get_mode();
    477     }
    478 
    479     for(int i = 0; i < q; i++)
    480         cout << ans[i] << endl;
    481 }
    482 
    483 mt19937 rnd(1);
    484 
    485 int main() {
    486     ios::sync_with_stdio(0);
    487     cin.tie(0);
    488 //    freopen("input.txt", "r", stdin);
    489 
    490     solve();
    491 }
    492 ```