Codeforces Round514 Div2 D & E

Problem D

Solution: This is a pretty interesting one. At first glance, we have a initial idea to do a binary search on the result. It seems pretty reasonable to have a solution run in $\mathcal{O}(\mathrm{n}\log(\mathrm{C}))$.Therefore, we only have to figure out a way to check the answer within $\mathcal{O}(\mathrm{n})$ amount of time. We observe the property of these dots and the center of the circule to be drawn. First of all the center must be on the line $\mathrm{y} = \mathrm{r}$, where $\mathrm{r}$ is the radius. Secondly, it seems to hard to figure out the point and check the points. Then, we can reverse this process by first looking at the points. If we first get all possible segments on $\mathrm{y} = \mathrm{r}$, then check if the segments are valid, this problem can be solved. By word “segments”, I mean the intersections of circles with center on each point and with radius $\mathrm{r}$. If the segment finally get is valid, it means that in the dots in the range of the segments have a distance less or equal to the radius. Therefore, they can be included in a circle.

using namespace std;
const int maxn = 2e5 + 10;
int n;
struct pt{
    double x,y;
} a[maxn];

bool possible(double x){
    double l = -1e18, r = 1e18;
    for(int i = 1; i <= n; i++){
        if(a[i].y > 2.0 * x) return false;
        double t = sqrt(a[i].y * (2 * x - a[i].y));
        l = max(l, a[i].x - t);
        r = min(r, a[i].x + t);
    }
    return l < r;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    bool pos,neg;
    pos = neg = false;
    for(int i = 1; i <= n; i++) {
        cin>>a[i].x>>a[i].y;
        if(a[i].y > 0) pos = 1;
        if(a[i].y < 0) neg = 1;
    }
    if(pos && neg) {
        cout<<-1<<endl;
        exit(0);
    }
    for(int i = 1; i <= n; i++) a[i].y = abs(a[i].y);
    double l = 0;
    double r = 1e16;
    int cnt = 300;
    while(cnt--){
        double mid = (r + l) / 2.0;
        if(possible(mid)) r = mid;
        else l = mid;
    }
    cout<<fixed<<setprecision(10)<<l<<endl;
    return 0;
}

Problem E

Solution: It is a greedy + dp problem. We first observe the properties of this problem. One vertex can either be in a new chain or be in an old chain. Therefore, at every vertex $\mathrm{v}$, it is possible to start with it or include it into a chain that has been already constructed. Therefore, we can first calculate the furthest vertex one can get for every vertex. Then, we perform a greedy solution to assign each vertex to a part of a chain by requiring that the deepest vertices go first.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
typedef pair<int,int> pii;
ll n,L,S,w[maxn],fa[maxn],lca[maxn][20],dep[maxn],top[maxn],use[maxn],ans;
ll sum[maxn];
vector<int> G[maxn];

void dfs1(int u){
    sum[u] = sum[fa[u]] + w[u];
    dep[u] = dep[fa[u]] + 1;
    int dis = L;
    top[u] = u;
    for(int k = 20; k >= 0; k--){
        int f = lca[top[u]][k];
        if(!f || (1 << k) >= dis) continue;
        if(sum[u] - sum[f] + w[f] > S) continue;
        dis -= (1 << k);
        top[u] = f;
    }
    for(int v: G[u]) dfs1(v);
}

void dfs2(int u){
    int best = -1;
    for(int v : G[u]){
        dfs2(v);
        if(use[v] == v) continue;
        if(best == -1 || dep[best] > dep[use[v]]) best = use[v];
    }
    if(best == -1) {
        best = top[u];
        ans++;
    }
    use[u] = best;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>L>>S;
    for(int i = 1; i <= n; i++) {
        cin>>w[i];
        if(w[i] > S) {
            cout<<-1<<endl;
            exit(0);
        }
    }
    for(int i = 2; i <= n; i++){
        cin>>fa[i];
        G[fa[i]].emplace_back(i);
        lca[i][0] = fa[i];
    }
    for(int i = 1; (1 << i) <= n; i++){
        for(int j = 1; j <= n; j++){
            lca[j][i] = lca[lca[j][i - 1]][i - 1];
        }
    }
    dfs1(1);
    dfs2(1);
    cout<<ans<<endl;
    return 0;
}