Submission #4358833


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct Reroot {
    using T = ll;
    T def = 0;
    T comp(T from, T to) {
        return max(from, to + 1);
    }

    void dfs1(int cu, int pa = -1) {
        dp[cu] = def;
        fore(to, E[cu]) if (to != pa) {
            dfs1(to, cu);
            dp[cu] = comp(dp[cu], dp[to]);
        }
    }
    void dfs2(int cu, int pa = -1) {
        res[cu] = def;
        fore(to, E[cu]) res[cu] = comp(res[cu], dp[to]);

        int n = E[cu].size();
        vector<T> lft(n), rht(n);
        lft[0] = dp[E[cu][0]] + 1;
        rep(i, 1, n) lft[i] = comp(lft[i - 1], dp[E[cu][i]]);
        rht[n - 1] = dp[E[cu][n - 1]] + 1;
        rrep(i, n - 2, 0) rht[i] = comp(rht[i + 1], dp[E[cu][i]]);

        T bak = dp[cu];
        rep(i, 0, n) if (E[cu][i] != pa) {
            if (n == 1) dp[cu] = def;
            else if (i == 0) dp[cu] = rht[1];
            else if (i == n - 1) dp[cu] = lft[n - 2];
            //else dp[cu] = comp(lft[i - 1], rht[i + 1]);
            else dp[cu] = max(lft[i - 1], rht[i + 1]);

            dfs2(E[cu][i], cu);
        }
        dp[cu] = bak;
    }







    int N; vector<vector<int>> E; vector<T> dp, res;
    Reroot() { }
    Reroot(int n) { init(n); }
    void init(int n) { N = n; E.clear(); E.resize(0); E.resize(n); }
    int Load() {
        cin >> N;
        init(N);
        rep(i, 0, N - 1) {
            int a, b; cin >> a >> b; a--; b--;
            add(a, b);
        }
        return N;
    }
    void add(int a, int b) { E[a].push_back(b); E[b].push_back(a); }
    vector<T> build() {
        dp.resize(N);
        res.resize(N);
        dfs1(0);
        dfs2(0);
        return res;
    }
};
template<class V> struct BIT {
    BIT() {}  // [L, R)
    int NV;vector<V> bit;
    BIT(int n){ init(n); }
    void init(int n) { NV = 1; while (NV < n)NV *= 2; bit.resize(NV); clear(); }
    V operator[](int e) { V s = 0; e++; while (e) s += bit[e - 1], e -= e&-e; return s; }
    void add(int e, V v) { e++; while (e <= NV) bit[e - 1] += v, e += e&-e; }
    int lower_bound(V val) { 
        V tv = 0; int i, ent = 0; for (i = NV - 1; i >= 0; i--)
        if(tv+bit[ent+(1<<i)-1]<=val)tv+=bit[ent+(1<<i)-1],ent += (1 << i);return ent;
    }
    V get(int L, int R) {
        assert(0 <= L); assert(R <= NV); assert(L <= R);
        V res = 0; if(R) res += operator[](R - 1); if (L) res -= operator[](L - 1);return res;
    }
    void clear() { rep(i, 0, NV) bit[i] = 0; }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/







//---------------------------------------------------------------------------------------------------
void _main() {
    int N, M;

    Reroot rr1, rr2;

    N = rr1.Load();
    vector<ll> dist1 = rr1.build();

    M = rr2.Load();
    vector<ll> dist2 = rr2.build();

    ll ma = -1;
    rep(i, 0, N) chmax(ma, dist1[i]);
    rep(i, 0, M) chmax(ma, dist2[i]);

    BIT<ll> bit1(101010), bit2(101010);
    rep(i, 0, N) bit1.add(dist1[i], 1);
    rep(i, 0, M) bit2.add(dist2[i], 1);
    ll other = 0;

    ll ans = 0;
    rep(i, 0, N) {
        ll ng = 0;
        if(0 <= ma - dist1[i]) ng = bit2.get(0, ma - dist1[i]);
        other += ng;
        ans += dist1[i] * (M - ng);
    }
    rep(i, 0, M) {
        ll ng = 0;
        if (0 <= ma - dist2[i]) ng = bit1.get(0, ma - dist2[i]);
        other += ng;
        ans += dist2[i] * (N - ng);
    }
    ans += ma * other / 2;
    ans += 1LL * (1LL * N * M - other / 2);
    cout << ans << endl;
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 700
Code Size 4741 Byte
Status
Exec Time 143 ms
Memory 25856 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 700 / 700 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt
Case Name Status Exec Time Memory
01.txt 3 ms 2304 KB
02.txt 3 ms 2304 KB
11.txt 2 ms 2304 KB
12.txt 3 ms 2304 KB
13.txt 3 ms 2304 KB
14.txt 2 ms 2304 KB
15.txt 2 ms 2304 KB
16.txt 3 ms 2304 KB
17.txt 2 ms 2304 KB
18.txt 3 ms 2304 KB
19.txt 3 ms 2304 KB
20.txt 3 ms 2304 KB
21.txt 112 ms 18176 KB
22.txt 108 ms 18504 KB
23.txt 116 ms 18176 KB
24.txt 126 ms 23552 KB
25.txt 104 ms 18912 KB
26.txt 111 ms 18384 KB
27.txt 122 ms 23632 KB
28.txt 121 ms 18048 KB
29.txt 121 ms 23680 KB
30.txt 143 ms 25472 KB
31.txt 114 ms 18176 KB
32.txt 112 ms 18576 KB
33.txt 115 ms 18176 KB
34.txt 129 ms 25856 KB
35.txt 102 ms 18728 KB
36.txt 113 ms 18320 KB
37.txt 123 ms 22288 KB
38.txt 113 ms 18048 KB
39.txt 126 ms 22528 KB
40.txt 131 ms 22656 KB
41.txt 58 ms 10240 KB
42.txt 58 ms 10240 KB
43.txt 56 ms 10240 KB
44.txt 58 ms 10240 KB
45.txt 53 ms 10640 KB
46.txt 53 ms 10580 KB
47.txt 68 ms 17536 KB
48.txt 60 ms 10240 KB
49.txt 67 ms 14080 KB
50.txt 66 ms 14080 KB