---
# System prepended metadata

title: 2022-2023 ICPC Northwestern European Regional Programming Contest (NWERC 2022)

---

2022-2023 ICPC Northwestern European Regional Programming Contest (NWERC 2022)
===
比賽鏈結
---
https://codeforces.com/gym/104875

比賽影片
---

{%youtube VsYpz2c1pd8%}

記分板
---
![image](https://hackmd.io/_uploads/rkegCXB01kg.png)



題解
---
### A. Alternating Algorithm
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### B. Bottle Flip
---
#### 題目摘要
一圓柱裡有空氣和水，給你高、半徑、空氣密度及水密度，求最低重心發生時的水高度

#### 想法
帶公式三分搜

:::spoiler 實作

```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
 
ld h, _, da, dw;
 
const ld eps = 1e-6;
 
ld calc(ld x){
    return (x * x * dw + (h - x) * (h - x) * da) / (x * dw + (h - x) * da);
}
 
int main() {
    cin >> h >> _ >> da >> dw;
    ld l = 0, r = h;
    while (r - l > eps) {
        ld ml = l + (r - l) / 3, mr = r - (r - l) / 3;
        if (calc(ml) < calc(mr)) r = mr;
        else l = ml;
    }
    cout << fixed << setprecision(10) << l << '\n';
}
```
:::


### C. Circular Caramel Cookie
---
#### 題目摘要
給一個面積$s$，求最小半徑使得鬆餅上的格子**大於**$s$。

#### 想法

對半徑二分搜後，花$\sqrt s$的時間檢查就好，想有夠久，太笨。
切記大於

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back 
 
const ld pi = acos(-1);
const ld eps = 2e-6;
 
 
int main() {
    ll s; cin >> s;
    ld l = 1, r = 1000000;
    while (r - l > eps) {
        ll tot = 0;
        ld mid = (l + r) / 2;
        rep (i, 1, 1000000) {
            if (i > mid) break;
            tot += (ll)sqrtl(mid * mid - double(i * i));
        }
        tot *= 4;
        if (tot > s) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(10);
    cout << r << '\n';
}
```
:::

### D. Delft Distance
---
#### 題目摘要
一張$h\times w$的圖中每格會是圓形或正方形，求從左上到右下不切到圓形或正方形的最短路
#### 想法
對每個格子點的一半多建點，並對所有點對它右、右下及下面的點建邊權，並用dp轉移

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
#define pi acos(-1)
 
const int N=1005;
const ld INF=1e18;
char s[N][N];
ld dis[4][N<<1][N<<1];
ld ans[N<<1][N<<1];
 
int main() {
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        cin >> s[i][j];
        if (s[i][j]=='X'){
            dis[0][i<<1][j<<1]=0.5;
            dis[1][i<<1][j<<1]=INF;
            dis[2][i<<1][j<<1]=0.5;
            dis[0][i<<1][j<<1|1]=0.5;
            dis[1][i<<1][j<<1|1]=1.0;
            dis[2][i<<1][j<<1|1]=INF;
            dis[0][i<<1|1][j<<1]=INF;
            dis[1][i<<1|1][j<<1]=1.0;
            dis[2][i<<1|1][j<<1]=0.5;
        }else{
            dis[0][i<<1][j<<1]=0.5;
            dis[1][i<<1][j<<1]=INF;
            dis[2][i<<1][j<<1]=0.5;
            dis[0][i<<1][j<<1|1]=0.5;
            dis[1][i<<1][j<<1|1]=pi/4;
            dis[2][i<<1][j<<1|1]=INF;
            dis[0][i<<1|1][j<<1]=INF;
            dis[1][i<<1|1][j<<1]=pi/4;
            dis[2][i<<1|1][j<<1]=0.5;
        }
    }
    for(int i=0;i<n;i++){
        dis[2][i<<1][m<<1]=0.5;
        dis[2][i<<1|1][m<<1]=0.5;
    }
    for(int j=0;j<m;j++){
        dis[0][n<<1][j<<1]=0.5;
        dis[0][n<<1][j<<1|1]=0.5;
    }
    for(int i=0;i<=(n<<1);i++) for(int j=0;j<=(m<<1);j++) ans[i][j]=INF;
    ans[0][0]=0;
    for(int i=0;i<=(n<<1);i++){
        for(int j=0;j<=(m<<1);j++){
            if (ans[i][j]>=INF) continue;
            if (dis[0][i][j]!=INF) ans[i][j+1]=min(ans[i][j+1], ans[i][j]+dis[0][i][j]);
            if (dis[1][i][j]!=INF) ans[i+1][j+1]=min(ans[i+1][j+1], ans[i][j]+dis[1][i][j]);
            if (dis[2][i][j]!=INF) ans[i+1][j]=min(ans[i+1][j], ans[i][j]+dis[2][i][j]);
        }
    }
    cout << fixed << setprecision(10)<< ans[n<<1][m<<1]*10 << '\n';
}
```
:::

### E. ETA
---
#### 題目摘要
 
給$\frac{p}{q}, \ \gcd(p, q) = 1$，構造出一個$n$點$m$邊的圖使得每個點走到$1$的最短路期望值為$\frac{p}{q}$

#### 想法

注意到我們最終只要構出一棵樹就好。
由於能輸出的$n$有一定限制，不妨去枚舉所有可能的$n$，也就是去枚舉每個$q$的倍數，這時候得到的資訊$\ p'\,$為$1$到所有點的路徑長度和
考慮最長能構出來的路徑和為一條鍊，也就是$\frac{(n - 1)n}{2}$，如果這個小於$p'$那就爛掉，再考慮最短的路徑和為全部都深度$1$，如果$p'<n-1$也爛掉。
接著就保證有解了，只要從一條鍊開始，好好將深度從深到淺做一些移動來彌補跟$p'$差距就好。
如果一直找都沒有就無解。

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back 

const ld pi = acos(-1);

int main() {
    ll a, b; scanf("%lld/%lld", &a, &b);
    for (int n = b; n <= 1000000; n += b) {
        ll dis = 1LL * a * (n / b), cur = 1LL * (n - 1) * n / 2; 
        if (dis > cur || dis < n - 1) continue;
        // cout << cur << ' ' << dis << '\n';
        ll d = cur - dis;
        vector<int> dep(n);
        iota(all(dep), 0);
        for (int i = n - 1; i > 1; --i) {
            if (d == 0) continue;
            int ok = dep[i] - 1;
            if (d <= ok) {
                dep[i] -= d;
                d = 0;
                break;
            } else {
                dep[i] = 1;
                d -= ok;
            }
        }
        vector<vector<int>> layer(n);
        rep (i, 0, n) {
            layer[dep[i]].pb(i);
        }
        cout << n << ' ' << n - 1 << '\n';
        rep (i, 1, n) {
            if (layer.empty()) break;
            for (int x : layer[i]) {
                cout << layer[i - 1].back() + 1 << ' ' << x + 1 << '\n';
            }
        }
        exit(0);
    }
    cout << "impossible\n" << '\n';
}
```
:::

### F. Faster Than Light
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=

```
:::

### G. Going in Circles
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=

```
:::


### H. High-quality Tree
---
#### 題目摘要
對於一個二元平衡樹，定義為所有點的左子樹最深深度與右子樹最深深度相差不超過1。給你一顆二元樹，求最少要刪多少點使其變成二元平衡樹

#### 想法
利用分治的想法，先遞迴左子樹使其變平衡樹，再做右子樹，最後看兩者的最深深度(不含被刪除點)，若兩者差>1，對深度深的子樹刪適當的點，因為每個點被刪掉次數只有一次，所以直接暴力刪點就好，複雜度$O(n)$

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
const int N=2e5+10;
vector<int> v[N];
int ch[2][N];
int dep[N], mxd[N], cnt[N];
bool del[N];
int ans;
 
void dfs(int x, int p, int d){
    cnt[x]=1;
    dep[x]=mxd[x]=d;
    for(auto e:v[x]) if (e!=p){
        if (ch[0][x]==0) ch[0][x]=e;
        else ch[1][x]=e;
        dfs(e, x, d+1);
        cnt[x]+=cnt[e];
        mxd[x]=max(mxd[x], mxd[e]);
    }
}
 
void dfs3(int x, int d){
    if (del[x]) return;
    if (dep[x]>=d){
        del[x]=1;
        ans++;
    }
    if (!del[ch[0][x]]) dfs3(ch[0][x], d);
    if (!del[ch[1][x]]) dfs3(ch[1][x], d);   
}
 
void dfs2(int x){
    int d0=dep[x], d1=dep[x];
    if (!del[ch[0][x]]) dfs2(ch[0][x]), d0=mxd[ch[0][x]];
    if (!del[ch[1][x]]) dfs2(ch[1][x]), d1=mxd[ch[1][x]];
    if (d0<d1) swap(d0, d1), swap(ch[0][x], ch[1][x]);
    if (d0-d1>1){
        dfs3(ch[0][x], d1+2);
    }
    mxd[x]=min(d0, d1+1);
}
 
int main(){
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ans=0;
    del[0]=1;
    dfs(1, 0, 1);
    dfs2(1);
    cout << ans << '\n';
}
```
:::

### I. Interview Question
---
#### 題目摘要
若一數是$x$的倍數要輸出Fizz，是$y$的倍數數出Buzz，是兩者的倍數輸出FizzBuzz，否則輸出該數，給你$l到r$的輸出，輸出任意一組$x,\ y$
#### 想法
若Fizz(FizzBuzz)出現2次以上，則$x$是最近的兩者差，若出現1次，直接將$x$設為該數，否則直接設成$r+1$，Buzz同理
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
 
int main() {
    int l, r; cin >> l >> r;
    int a1=-1, b1=-1, a2=-1, b2=-1;
    for(int i=l;i<=r;i++){
        string s;
        cin >> s;
        if (s=="Fizz"){
            if (a1==-1) a1=i;
            else if (a2==-1) a2=i;
        }else if (s=="Buzz"){
            if (b1==-1) b1=i;
            else if (b2==-1) b2=i;
        }else if (s=="FizzBuzz"){
            if (a1==-1) a1=i;
            else if (a2==-1) a2=i;
            if (b1==-1) b1=i;
            else if (b2==-1) b2=i;
        }
    }
    if (a1==-1&&a2==-1){
        cout << r+1 << ' ';
    }else if (a2==-1){
        cout << a1 << ' ';
    }else{
        cout << a2-a1 << ' ';
    }
    if (b1==-1&&b2==-1){
        cout << r+1 << '\n';
    }else if (b2==-1){
        cout << b1 << '\n';
    }else{
        cout << b2-b1 << '\n';
    }
}
```
:::


### J. Justice Served
---
#### 題目摘要
給好多區間，該區間的答案是所有包覆該區間的答案的最大值+1，位被任何區間包覆答案是0，求所有區間答案
#### 想法
先對左端排序，若有人包覆我代表在我之前有人的右端比我的右端大，因此開個線段樹，藉由右界以後的最大值找到目前這線段的答案，再對右界位置單點改成線段答案就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pii;
 
vector<int> v;
inline int id(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
 
const int N=4e5+10;
int t[N<<2];
vector<tuple<int, int, int>> p;
int ans[N];
 
void modify(int v, int l, int r, int x, int k){
    if (x==l&&x==r){
        t[v]=k;
        return;
    }
    int m=l+r>>1;
    if (x<=m) modify(v<<1, l, m, x, k);
    else modify(v<<1|1, m+1, r, x, k);
    t[v]=max(t[v<<1], t[v<<1|1]);
}
 
int query(int v, int l, int r, int ql, int qr){
    if (ql<=l&&r<=qr) return t[v];
    int m=l+r>>1;
    int res=0;
    if (ql<=m) res=max(res, query(v<<1, l, m, ql, qr));
    if (qr>m) res=max(res, query(v<<1|1, m+1, r, ql, qr));
    return res;
}
 
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int a, t;
        cin >> a >> t;
        v.push_back(a);
        v.push_back(a+t);
        p.push_back({a, a+t, i});
    }
    sort(v.begin(), v.end());
    sort(p.begin(), p.end(), [](auto a, auto b){
        auto [l1, r1, i1]=a;
        auto [l2, r2, i2]=b;
        if (l1==l2) return r1>r2;
        return l1<l2;
    });
    int sz=v.size();
    for(auto [l, r, idx]:p){
        ans[idx]=query(1, 1, sz, id(r), sz)+1;
        modify(1, 1, sz, id(r), ans[idx]);
    }
    for(int i=0;i<n;i++) cout << ans[i]-1 << ' ';
    cout << '\n';
}

```
:::


### K. Kebab Pizza
---
#### 題目摘要
$N$塊披薩及$K$種配料，每塊披薩上有兩種配料(可能相同)，加配料時必須連續加一段環狀區間，給你每個披薩上的配料(無序)問能不能達成。

#### 想法
轉換為圖論問題，把披薩看做邊，配料看做點。
顯然，一開始可以先將垃圾重邊給去掉。
考慮一種impossible的情況：如果一個點$v$連著三個以上非葉節點的點，那麼他一定是爛的。
原因是在任兩塊含$v$披薩中都會需要放其他配料的披薩，因此配料$v$無法連續。
接下來，會發現需要用到環狀性質的只有環，如果出現其他連通塊會幹到他用結尾連起來$(ex: (1, 2),\, (2, 3),\, (3, 1),\, (4, 5))$
因此若出現一個環，整張圖必須為一塊連通圖，否則impossible。反之各連通塊都無環就OK。
特別注意幾個很靠北的地方：
1. 自環
2. 若連到自環請注意自環不是葉節點
3. 會有沒有度數的點，不要在判連通圖時考慮它
4. 自環不是沒有度數的點

:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back 

const int MAXN = 1e5 + 5;

int pa[MAXN], sz[MAXN], edge[MAXN];

int find(int x) {
    return x == pa[x] ? pa[x] : pa[x] = find(pa[x]);
}

bool Union(int a, int b) {
    a = find(a), b = find(b);
    edge[a]++;
    if (a == b) return false;
    sz[a] += sz[b];
    edge[a] += edge[b];
    pa[b] = a;
    return true;
}

int main() {
    int n, k; cin >> n >> k;
    vector<pii> tp(n);
    for (auto &[a, b] : tp) {
        cin >> a >> b;
        a--, b--;
        if (a > b) swap(a, b);
    }
    sort(all(tp));
    tp.erase(unique(all(tp)), tp.end());
    vector<vector<int>> adj(k);
    iota(pa, pa + k, 0);
    fill(sz, sz + k, 1);
    for (auto [a, b] : tp) {
        adj[a].pb(b);
        if (a != b) {
            adj[b].pb(a);
            Union(a, b);
        }
    }
    rep (i, 0, k) {
        if (adj[i].size() >= 3) {
            int cnt = 0;
            for (int x : adj[i]) {
                if (x == i) continue;
                cnt += adj[x].size() > 1;
            }
            if (cnt >= 3) {
                cout << "impossible\n";
                exit(0);
            }
        }
    }
    int cyc = 0, cc = 0;
    rep (i, 0, k) if (i == find(i)) {
        if (adj[i].empty()) continue;
        cc++;
        cyc += sz[i] <= edge[i];
    }
    if (cc <= 1 || cyc == 0) cout << "possible\n";
    else cout << "impossible\n";
}
```
:::

### L. Last Guess
---
#### 題目大綱
玩wordle，保證過程是好的以及有解，玩了n-1次後，輸出有可能的其中一組解
#### 想法
對於一組解答，會有以下的限制：
* 綠色代表一定是那個字母
* 黑色代表這個字母不可能在這裡出現
* 一個字母出現的次數下界會是在所有詢問中(綠色+黃色)最多的次數
    * 其中，若一個字母在一次詢問中同時出現了綠黃黑，代表這個字母在答案出現的次數會恰好[上界 = 下界]是(綠+黃)

因此，可以考慮建最大流模型：

每個位置連邊到匯點流量為1，對於每個字母，對每個位置去記錄他可不可以放在這，可以就連流量為1的邊。

最後要來處理出現上下界問題，可以考慮多建一個點s'，先將源點向每個字母建流量為字母下界的邊，再從s'向每個字母建(上界-下界)流量的邊，最後從s往s'建流量為$m - \sum {下界}$的邊就能很好的完成下界流的要求，

構造答案就檢查字母和位置中間的流量有沒有被流滿就好。
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

template <typename T>
struct Dinic {
    
    const T INF = numeric_limits<T>::max() / 2;

    struct edge {
        int v, r; T rc;
    };

    vector<vector<edge>> adj;
    vector<int> dis, it;
    Dinic(int n) : adj(n), dis(n), it(n) {}

    void add_edge(int u, int v, T c) {
        adj[u].pb({v, adj[v].size(), c});
        adj[v].pb({u, adj[u].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(all(dis), IINF);
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const auto& [v, r, rc] : adj[u]) {
                if (dis[v] < IINF || rc == 0) continue;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
        return dis[t] < IINF;
    }

    T dfs(int u, int t, T cap) {
        if (u == t || cap == 0) return cap;
        for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
            auto &[v, r, rc] = adj[u][i];
            if (dis[v] != dis[u] + 1) continue;
            T tmp = dfs(v, t, min(cap, rc));
            if (tmp > 0) {
                rc -= tmp;
                adj[v][r].rc += tmp;
                return tmp;
            }
        }
        return 0;
    }

    T flow(int s, int t) {
        T ans = 0, tmp;
        while (bfs(s, t)) {
            fill(all(it), 0);
            while ((tmp = dfs(s, t, IINF)) > 0) {
                ans += tmp;
            }
        }
        return ans;
    }

    bool inScut(int u) { return dis[u] < IINF; }
};

void solve() {
    int n, m; cin >> n >> m;
    vector<int> hi(26, m), lo(26, 0);
    vector no(26, vector<bool>(m, 0));
    vector<bool> vis(m, 0);
    auto yes = no;
    rep (i, 0, n - 1) {
        vector<int> g(26, 0), b(26, 0), y(26, 0);
        vector<int> cnt(26, 0);
        string s, t; cin >> s >> t;
        rep (j, 0, m) {
            if (t[j] == 'G') {
                vis[j] = 1;
                yes[s[j] - 'a'][j] = 1;
                cnt[s[j] - 'a']++;
            } else if (t[j] == 'B') {
                no[s[j] - 'a'][j] = 1;
            } else {
                no[s[j] - 'a'][j] = 1;
                cnt[s[j] - 'a']++;
            }
        }
        rep (j, 0, 26) {
            if (count(all(s), 'a' + j) != cnt[j]) {
                lo[j] = hi[j] = cnt[j];
            } else {
                chmax(lo[j], cnt[j]);
            }
        }
    }
    Dinic<int> G(26 + m + 3);
    int s = 26 + m, t = s + 1, s2 = t + 1;
    int tot = 0;
    rep (i, 0, 26) {
        G.add_edge(s, i, lo[i]);
        G.add_edge(s2, i, hi[i] - lo[i]);
        tot += lo[i];
        rep (j, 0, m) {
            if (yes[i][j]) {
                G.add_edge(i, 26 + j, 1);
                continue;
            }
            if (no[i][j] || vis[j]) continue;
            G.add_edge(i, 26 + j, 1);
        }
    }
    rep (i, 0, m) G.add_edge(26 + i, t, 1);
    G.add_edge(s, s2, m - tot);
    G.flow(s, t);
    string ans(m, '#');
    rep (i, 0, 26) {
        for (auto [v, r, rc] : G.adj[i]) {
            if (v != s && v != s2 && rc == 0) ans[v - 26] = char('a' + i);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::