Codeforces Round #660 Editorial
Difference between en2 and en3, changed 266 character(s)
[problem:1388A]↵
 ↵
Idea: [user:Denisov,2020-07-30]↵

<spoiler summary="Tutorial">↵
[tutorial:1388A]↵
</spoiler>↵

<spoiler summary="Solution (Karavaev1101)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main(){↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(nullptr); cout.tie(nullptr);↵

    int q;↵
    cin >> q;↵

    while(q--){↵
        int n; cin >> n;↵
        if(n <= 30){↵
            cout << "NO" << endl;↵
        }↵
        else{↵
            cout << "YES" << endl;↵
            if(n == 36 || n == 40 || n == 44){↵
                cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl;↵
            }↵
            else{↵
                cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl;↵
            }↵
        }↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[problem:1388B]↵
 ↵
Idea: [user:Karavaev1101,2020-07-30]↵

<spoiler summary="Tutorial">↵
[tutorial:1388B]↵
</spoiler>↵

<spoiler summary="Solution (Karavaev1101)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(nullptr); cout.tie(nullptr);↵

    int q;↵
    cin >> q;↵

    while (q--) {↵
        int n; cin >> n;↵
        int x = (n + 3) / 4;↵
        for (int i = 0; i < n - x; ++i) {↵
            cout << 9;↵
        }↵
        for (int i = 0; i < x; ++i) {↵
            cout << 8;↵
        }↵
        cout << endl;↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[problem:1388C]↵
 ↵
Idea: [user:Karavaev1101,2020-07-30]↵

<spoiler summary="Tutorial">↵
[tutorial:1388C]↵
</spoiler>↵

<spoiler summary="Solution (Karavaev1101)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int N = 1e5 + 7;↵

vector < int > gr[N];↵

bool access = true;↵

int p[N], h[N], a[N], g[N];↵

void dfs(int v, int ancestor = -1) {↵
    a[v] = p[v];↵
    int sum_g = 0;↵
    for (int to : gr[v]) {↵
        if (to == ancestor) continue;↵
        dfs(to, v);↵
        sum_g += g[to];↵
        a[v] += a[to];↵
    }↵
    if ((a[v] + h[v]) % 2 == 0) {} // first↵
    else access = false;↵
    g[v] = (a[v] + h[v]) / 2;↵
    if (g[v] >= 0 && g[v] <= a[v]) {} // second↵
    else access = false;↵
    if (sum_g <= g[v]) {} // third↵
    else access = false;↵
}↵

int main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(nullptr); cout.tie(nullptr);↵

    int q;↵
    cin >> q;↵

    while (q--) {↵
        int n, m; cin >> n >> m;↵
        for (int i = 0; i < n; ++i) cin >> p[i];↵
        for (int i = 0; i < n; ++i) cin >> h[i];↵
        for (int i = 0; i < n - 1; ++i) {↵
            int a, b; cin >> a >> b;↵
            --a, --b;↵
            gr[a].push_back(b);↵
            gr[b].push_back(a);↵
        }↵
        dfs(0);↵
        cout << (access ? "YES" : "NO") << endl;↵
        access = true;↵
        for (int i = 0; i < n; ++i) gr[i].clear();↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[problem:1388D]↵
 ↵
Idea: [user:Denisov,2020-07-30]↵

<spoiler summary="Tutorial">↵
[tutorial:1388D]↵
</spoiler>↵

<spoiler summary="Solution (Denisov)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define all(a) a.begin(),a.end()↵

using namespace std;↵

vector <vector <int> > edge;↵
vector <ll> a;↵
vector <int> b, used;↵
vector <int> order[2];↵
ll ans;↵
inline void dfs (int v) {↵
    used[v] = 1;↵
    for (int to : edge[v]) {↵
        if (!used[to]) dfs(to);↵
    }↵
    ans += a[v];↵
    if (b[v] != -1 && a[v] > 0) {↵
        a[b[v]] += a[v];↵
    }↵
    if (a[v] > 0) {↵
        order[0].push_back(v);↵
    }↵
    else {↵
        order[1].push_back(v);↵
    }↵
}↵
inline void solve () {↵
    for (auto &i : edge) i.clear();↵
    edge.clear();↵
    a.clear();↵
    order[0].clear();↵
    order[1].clear();↵
    b.clear();↵
    used.clear();↵
    int n, x;↵
    cin >> n;↵
    edge.resize(n);↵
    a.resize(n);↵
    b.resize(n);↵
    for (auto &i : a) cin >> i;↵
    for (int i = 0; i < n; i++) {↵
        cin >> x;↵
        if (x != -1) {↵
            --x;↵
            edge[x].push_back(i);↵
        }↵
        b[i] = x;↵
    }↵
    ans = 0;↵
    used.assign(n, 0);↵
    for (int i = 0; i < n; i++) {↵
        if (!used[i]) {↵
            dfs(i);↵
        }↵
    }↵
    cout << ans << '\n';↵
    reverse(all(order[1]));↵
    for (auto &i : order[0]) cout << i + 1 << ' ';↵
    for (auto &i : order[1]) cout << i + 1 << ' ';↵
    cout << '\n';↵
}↵
main()↵
{↵
    ios::sync_with_stdio(0);↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    solve();↵
}↵

~~~~~↵

</spoiler>↵

<spoiler summary="Solution (Karavaev1101)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵

#define int long long↵

#define Vanya Unstoppable↵

using namespace std;↵

signedint main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(nullptr); cout.tie(nullptr);↵
    ↵
    int 
qn;↵
    cin >> 
qn;↵
    ↵
    
while (q--) {↵
        int n; cin >> n;↵
        int
long long a[n];↵
        for (int i = 0; i < n; ++i) {↵
        
    cin >> a[i];↵
        }↵
    

    set < int > s;↵
        for (int i = 0; i < n; ++i) {↵
        
    s.insert(i);↵
        }↵
    

    int b[n];↵
        vector < int > sz(n);↵
        for (int i = 0; i < n; ++i) {↵
        
    cin >> b[i]; --b[i];↵
        
    if (b[i] == -2) continue;↵
        
    ++sz[b[i]];↵
        
    if (sz[b[i]] == 1) {↵
            
    s.erase(b[i]);↵
        
    }↵
    
}↵
    }
    
    intlong long sum = 0;↵
        vector < int > ans[2];↵
    

    while (!s.empty()) {↵
            int v = *s.begin();↵
            s.erase(s.begin());↵
            int w = b[v];↵
            sum += a[v];↵
            if (a[v] >= 0) {↵
                if (w >= 0) {↵
                    a[w] += a[v];↵
                }↵
                ans[0].push_back(v);↵
            } else {↵
                ans[1].push_back(v);↵
            }↵
            if (w >= 0) {↵
                --sz[w];↵
                if (sz[w] == 0) {↵
                    s.insert(w);↵
                }↵
            }↵
        }↵
    

    cout << sum << endl;↵
        for (int to : ans[0]) cout << to + 1 << ' ';↵
    

    reverse(ans[1].begin(), ans[1].end());↵
    

    for (int to : ans[1]) cout << to + 1 << ' ';↵
        cout << endl;↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[problem:1388E]↵
 ↵
Idea: [user:perekopskiy,2020-07-30]↵

<spoiler summary="Tutorial">↵
[tutorial:1388E]↵
</spoiler>↵

<spoiler summary="Solution (perekopskiy)">↵
 ↵
~~~~~↵
#include <bits/stdc++.h>↵

#define pb push_back↵
#define x first↵
#define y second↵

using namespace std;↵

const int N = 1e5 + 10;↵
const double eps = 1e-9;↵

double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x;↵
int ind_l, ind_r;↵

double point_pr(double x, double y, double ctg) {↵
    return x - y * ctg;↵
}↵

signed main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int n;↵
    vector<pair<double, int> > q;↵
    vector<pair<double, pair<int, int> > > events, prom_left, prom_right;↵
    cin >> n;↵
    pair<double, double> mx, mn;↵
    mx = {-1.0, -1.0};↵
    mn = {2e9, 2e9};↵
    mn_x = 2e9;↵
    mx_x = -2e9;↵
    for(int i = 0; i < n; ++i) {↵
        cin >> xl[i] >> xr[i] >> y[i];↵

        if(xl[i] < mn_x) {↵
            mn_x = xl[i];↵
        }↵
        if(xr[i] > mx_x) {↵
            mx_x = xr[i];↵
        }↵

        if(mx.y < y[i]) {↵
            mx.y = y[i];↵
            mx.x = xl[i];↵
            ind_l = i;↵
        }↵
        else if(mx.y == y[i] && mx.x > xl[i]) {↵
            mx.y = y[i];↵
            mx.x = xl[i];↵
            ind_l = i;↵
        }↵

        if(mn.y > y[i]) {↵
            mn.y = y[i];↵
            mn.x = xl[i];↵
            ind_r = i;↵
        }↵
        else if(mn.y == y[i] && mn.x < xl[i]) {↵
            mn.y = y[i];↵
            mn.x = xl[i];↵
            ind_r = i;↵
        }↵
    }↵
    double a1, a2;↵
    for(int i = 0; i < n; ++i) {↵
        for(int j = 0; j < n; ++j) {↵
            if(y[i] > y[j]) {↵
                a1 = (xr[i] - xl[j]) / (y[i] - y[j]);↵
                a2 = (xl[i] - xr[j]) / (y[i] - y[j]);↵
                q.pb({a1, 1});↵
                q.pb({a2, 2});↵

                a1 = (xl[i] - xl[j]) / (y[i] - y[j]);↵
                a2 = (xr[i] - xr[j]) / (y[i] - y[j]);↵
                events.pb({a1, {i, j}});↵
                events.pb({a2, {-i - 1, j}});↵
            }↵
        }↵
    }↵

    if(q.empty()) {↵
        cout << fixed << setprecision(9) << mx_x - mn_x << endl;↵
        return 0;↵
    }↵

    sort(q.rbegin(), q.rend());↵
    int cnt = 0;↵
    double last = 0;↵
    for(auto i : q) {↵
        if(i.y == 2) {↵
            --cnt;↵
            if(!cnt) {↵
                events.pb({i.x, {-1e9, -1e9}});↵
            }↵
        }↵
        else {↵
            if(!cnt) {↵
                events.pb({i.x, {-1e9, -1e9}});↵
            }↵
            ++cnt;↵
        }↵
    }↵
    sort(events.rbegin(), events.rend());↵
    double ans = 1e18, ang;↵
    last = -1e18;↵
    for(auto i : events) {↵
        if(i.y.x == i.y.y) {↵
            unordered_set<int> s;↵
            vector<int> to_check;↵
            for(auto j : prom_left) {↵
                s.insert(j.y.x);↵
                if(j.y.x == ind_l) {↵
                    to_check.pb(j.y.y);↵
                }↵
            }↵
            prom_left.clear();↵
            for(auto j : to_check) {↵
                if(!s.count(j)) {↵
                    ind_l = j;↵
                    break;↵
                }↵
            }↵
            s.clear();↵
            to_check.clear();↵

            for(auto j : prom_right) {↵
                s.insert(j.y.y);↵
                if(j.y.y == ind_r) {↵
                    to_check.pb(-j.y.x - 1);↵
                }↵
            }↵
            prom_right.clear();↵
            for(auto j : to_check) {↵
                if(!s.count(j)) {↵
                    ind_r = j;↵
                    break;↵
                }↵
            }↵
            s.clear();↵
            to_check.clear();↵

            double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x);↵
            if(ans > res) {↵
                ans = res;↵
                ang = i.x;↵
            }↵
        }↵
        else if(i.y.x < 0) {↵
            if(abs(i.x - last) > eps) {↵
                unordered_set<int> s;↵
                vector<int> to_check;↵
                for(auto j : prom_right) {↵
                    s.insert(j.y.y);↵
                    if(j.y.y == ind_r) {↵
                        to_check.pb(-j.y.x - 1);↵
                    }↵
                }↵
                prom_right.clear();↵
                for(auto j : to_check) {↵
                    if(!s.count(j)) {↵
                        ind_r = j;↵
                        break;↵
                    }↵
                }↵
                s.clear();↵
                to_check.clear();↵
            }↵
            prom_right.pb(i);↵
        }↵
        else {↵
            if(abs(i.x - last) > eps) {↵
                unordered_set<int> s;↵
                vector<int> to_check;↵
                for(auto j : prom_left) {↵
                    s.insert(j.y.x);↵
                    if(j.y.x == ind_l) {↵
                        to_check.pb(j.y.y);↵
                    }↵
                }↵
                prom_left.clear();↵
                for(auto j : to_check) {↵
                    if(!s.count(j)) {↵
                        ind_l = j;↵
                        break;↵
                    }↵
                }↵
                s.clear();↵
                to_check.clear();↵
            }↵
            prom_left.pb(i);↵
        }↵
        last = i.x;↵
    }↵
    cout << fixed << setprecision(9) << ans << endl;↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Karavaiev 2020-07-31 11:27:49 266
ru3 Russian Karavaiev 2020-07-31 11:25:52 266
ru2 Russian Karavaiev 2020-07-30 22:43:42 64
en2 English Karavaiev 2020-07-30 22:41:40 64
ru1 Russian Karavaiev 2020-07-30 20:47:31 11648 Первая редакция перевода на Русский
en1 English Karavaiev 2020-07-30 20:41:41 11664 Initial revision (published)