oj.uz

Submission #376510

# Submission time Handle Problem Language Result Execution time Memory
376510 2021-03-11T15:27:27 Z wiwiho Designated Cities (JOI19_designated_cities) C++14
100 / 100
 854 ms 79016 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int l = -1, r = -1;
    ll mx = 0, tag = 0;
    ll rv(){
        return mx + tag;
    }
};

struct SegmentTree{
    vector<Node> st;
    int ts = 0;

    SegmentTree(int sz): st(2 * sz) {}

    int build(int l, int r){
        int id = ts++;
        if(l == r) return id;
        int m = (l + r) / 2;
        st[id].l = build(l, m);
        st[id].r = build(m + 1, r);
        return id;
    }

    void modify(int l, int r, ll v, int L, int R, int id){
        if(l == L && r == R){
            st[id].tag += v;
            return;
        }
        int M = (L + R) / 2;
        if(r <= M) modify(l, r, v, L, M, st[id].l);
        else if(l > M) modify(l, r, v, M + 1, R, st[id].r);
        else{
            modify(l, M, v, L, M, st[id].l);
            modify(M + 1, r, v, M + 1, R, st[id].r);
        }
        st[id].mx = max(st[st[id].l].rv(), st[st[id].r].rv());
    }

    void push(int id){
        st[st[id].l].tag += st[id].tag;
        st[st[id].r].tag += st[id].tag;
        st[id].mx = st[id].rv();
        st[id].tag = 0;
    }

    int query(int L, int R, int id){
        if(L == R) return L;
        push(id);
        int M = (L + R) / 2;
        if(st[st[id].l].rv() >= st[st[id].r].rv()) return query(L, M, st[id].l);
        else return query(M + 1, R, st[id].r);
    }

    ll mx(){
        return st[0].rv();
    }
};

struct edge{
    ll a, b, c, d;
    ll get(int v){
        if(b == v) return c;
        else return d;
    }
    int ano(int v){
        return a ^ b ^ v;
    }
};

vector<vector<edge>> g;
vector<ll> dp, dp2, ans, up;

void dfs1(int now, int p){
    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p) continue;
        dfs1(v, now);
        dp[now] += dp[v] + i.get(v);
        dp2[now] = max(dp2[now], dp2[v] + i.get(v));
    }
}

void dfs2(int now, int p){
    vector<ll> tmp;
    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p){
            ans[now] = ans[p] - i.get(now) + i.get(p);
            continue;
        }
        tmp.eb(dp2[v] + i.get(v));
    }
    gsort(tmp);
    tmp.eb(0);

    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p){
            continue;
        }
        if(tmp[0] == dp2[v] + i.get(v)){
            if(tmp.size() >= 2) up[v] = tmp[1];
        }
        else up[v] = tmp[0];
        up[v] = max(up[v], up[now]) + i.get(now);
        dfs2(v, now);
    }
}

vector<int> in, out, pr;
int ts = 0;
vector<ll> pw;

void dfs3(int now, int p, ll w){
    pr[now] = p;
    pw[now] = w;
    in[now] = ++ts;
    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p) continue;
        dfs3(v, now, i.get(v));
    }
    out[now] = ts;
}

int main(){
    StarBurstStream

    int n;
    cin >> n;

    dp.resize(n + 1);
    dp2.resize(n + 1);
    ans.resize(n + 1);
    up.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    pr.resize(n + 1);
    pw.resize(n + 1);
    vector<ll> ans2(n + 1);

    g.resize(n + 1);
    for(int i = 0; i < n - 1; i++){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edge e({u, v, c, d});
        g[u].eb(e);
        g[v].eb(e);
    }

    dfs1(1, 1);
    ans[1] = dp[1];
    dfs2(1, 1);
//    printv(dp, cerr);
//    printv(dp2, cerr);
//    printv(ans, cerr);
//    printv(ans2, cerr);

    int rt = 1;
    for(int i = 2; i <= n; i++){
        ans2[i] = max(dp2[i], up[i]);
        if(ans[i] - ans2[i] < ans[rt] - ans2[rt]) rt = i;
    }

    dfs3(rt, rt, 0);

    SegmentTree st(n);
    st.build(1, n);
//    printv(pw, cerr);
//    printv(in, cerr);
//    printv(out, cerr);
    vector<int> id(n + 1);

    for(int i = 1; i <= n; i++){
        id[in[i]] = i;
        st.modify(in[i], out[i], pw[i], 1, n, 0);
    }
//    cerr << rt << "\n";

    vector<ll> a(n + 1);
    ll a1 = 1LL << 60;
    ll a2 = 1LL << 60;
    for(int i = 1; i <= n; i++) a1 = min(a1, ans[i]), a2 = min(a2, ans[i] - ans2[i]);
    int deg = 0;
    int cnt = 1;
    vector<bool> del(n + 1);
    del[rt] = true;
    ll tans = 0;
    while(st.mx() > 0){
        int now = id[st.query(1, n, 0)];
        ll tmx = st.mx(), tcnt = 0;
        tans += st.mx();
//        cerr << "test " << now << " " << st.mx() << "\n";
        while(!del[now]){
            del[now] = true;
            st.modify(in[now], out[now], -pw[now], 1, n, 0);
            tcnt += pw[now];
//            cerr << "del " << now << "\n";
            now = pr[now];
        }
        if(now == rt){
            deg++;
            if(deg == 2) cnt--;
        }
        cnt++;
//        cerr << cnt << " " << tans << "\n";
        a[cnt] = tans;
    }
    for(int i = 1; i <= n; i++) a[i] = max(a[i - 1], a[i]);
//    assert(a[2] <= ans2[rt]);
    assert(a[2] == ans2[rt]);
//    printv(a, cerr);
//    cerr << ans[rt] << "\n";

    int q;
    cin >> q;
    while(q--){
        int e;
        cin >> e;
        if(e == 1) cout << a1 << "\n";
        else if(e == 2) cout << a2 << "\n";
        else cout << ans[rt] - a[e] << "\n";
    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:242:12: warning: unused variable 'tmx' [-Wunused-variable]
  242 |         ll tmx = st.mx(), tcnt = 0;
      |            ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 645 ms 45932 KB Output is correct
3 Correct 673 ms 70764 KB Output is correct
4 Correct 614 ms 45932 KB Output is correct
5 Correct 692 ms 45660 KB Output is correct
6 Correct 742 ms 49900 KB Output is correct
7 Correct 632 ms 44764 KB Output is correct
8 Correct 774 ms 71532 KB Output is correct
9 Correct 592 ms 45640 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 672 ms 46060 KB Output is correct
3 Correct 665 ms 75568 KB Output is correct
4 Correct 613 ms 45804 KB Output is correct
5 Correct 666 ms 45916 KB Output is correct
6 Correct 702 ms 50540 KB Output is correct
7 Correct 585 ms 45512 KB Output is correct
8 Correct 806 ms 61548 KB Output is correct
9 Correct 553 ms 45640 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 4 ms 876 KB Output is correct
14 Correct 4 ms 1004 KB Output is correct
15 Correct 4 ms 876 KB Output is correct
16 Correct 5 ms 876 KB Output is correct
17 Correct 4 ms 876 KB Output is correct
18 Correct 4 ms 876 KB Output is correct
19 Correct 4 ms 876 KB Output is correct
20 Correct 4 ms 876 KB Output is correct
21 Correct 4 ms 876 KB Output is correct
22 Correct 4 ms 876 KB Output is correct
23 Correct 4 ms 876 KB Output is correct
24 Correct 4 ms 876 KB Output is correct
25 Correct 4 ms 1132 KB Output is correct
26 Correct 4 ms 888 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 645 ms 45932 KB Output is correct
3 Correct 673 ms 70764 KB Output is correct
4 Correct 614 ms 45932 KB Output is correct
5 Correct 692 ms 45660 KB Output is correct
6 Correct 742 ms 49900 KB Output is correct
7 Correct 632 ms 44764 KB Output is correct
8 Correct 774 ms 71532 KB Output is correct
9 Correct 592 ms 45640 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 672 ms 46060 KB Output is correct
12 Correct 665 ms 75568 KB Output is correct
13 Correct 613 ms 45804 KB Output is correct
14 Correct 666 ms 45916 KB Output is correct
15 Correct 702 ms 50540 KB Output is correct
16 Correct 585 ms 45512 KB Output is correct
17 Correct 806 ms 61548 KB Output is correct
18 Correct 553 ms 45640 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 667 ms 46060 KB Output is correct
21 Correct 641 ms 75628 KB Output is correct
22 Correct 600 ms 45804 KB Output is correct
23 Correct 708 ms 46316 KB Output is correct
24 Correct 638 ms 46444 KB Output is correct
25 Correct 657 ms 46372 KB Output is correct
26 Correct 695 ms 46444 KB Output is correct
27 Correct 624 ms 46176 KB Output is correct
28 Correct 697 ms 50028 KB Output is correct
29 Correct 694 ms 46700 KB Output is correct
30 Correct 617 ms 45524 KB Output is correct
31 Correct 592 ms 44500 KB Output is correct
32 Correct 854 ms 62956 KB Output is correct
33 Correct 585 ms 45640 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 645 ms 45932 KB Output is correct
14 Correct 673 ms 70764 KB Output is correct
15 Correct 614 ms 45932 KB Output is correct
16 Correct 692 ms 45660 KB Output is correct
17 Correct 742 ms 49900 KB Output is correct
18 Correct 632 ms 44764 KB Output is correct
19 Correct 774 ms 71532 KB Output is correct
20 Correct 592 ms 45640 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 672 ms 46060 KB Output is correct
23 Correct 665 ms 75568 KB Output is correct
24 Correct 613 ms 45804 KB Output is correct
25 Correct 666 ms 45916 KB Output is correct
26 Correct 702 ms 50540 KB Output is correct
27 Correct 585 ms 45512 KB Output is correct
28 Correct 806 ms 61548 KB Output is correct
29 Correct 553 ms 45640 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 4 ms 876 KB Output is correct
32 Correct 4 ms 1004 KB Output is correct
33 Correct 4 ms 876 KB Output is correct
34 Correct 5 ms 876 KB Output is correct
35 Correct 4 ms 876 KB Output is correct
36 Correct 4 ms 876 KB Output is correct
37 Correct 4 ms 876 KB Output is correct
38 Correct 4 ms 876 KB Output is correct
39 Correct 4 ms 876 KB Output is correct
40 Correct 4 ms 876 KB Output is correct
41 Correct 4 ms 876 KB Output is correct
42 Correct 4 ms 876 KB Output is correct
43 Correct 4 ms 1132 KB Output is correct
44 Correct 4 ms 888 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 667 ms 46060 KB Output is correct
47 Correct 641 ms 75628 KB Output is correct
48 Correct 600 ms 45804 KB Output is correct
49 Correct 708 ms 46316 KB Output is correct
50 Correct 638 ms 46444 KB Output is correct
51 Correct 657 ms 46372 KB Output is correct
52 Correct 695 ms 46444 KB Output is correct
53 Correct 624 ms 46176 KB Output is correct
54 Correct 697 ms 50028 KB Output is correct
55 Correct 694 ms 46700 KB Output is correct
56 Correct 617 ms 45524 KB Output is correct
57 Correct 592 ms 44500 KB Output is correct
58 Correct 854 ms 62956 KB Output is correct
59 Correct 585 ms 45640 KB Output is correct
60 Correct 1 ms 364 KB Output is correct
61 Correct 694 ms 55020 KB Output is correct
62 Correct 707 ms 79016 KB Output is correct
63 Correct 675 ms 53660 KB Output is correct
64 Correct 703 ms 55404 KB Output is correct
65 Correct 728 ms 53996 KB Output is correct
66 Correct 732 ms 55572 KB Output is correct
67 Correct 692 ms 54124 KB Output is correct
68 Correct 682 ms 55392 KB Output is correct
69 Correct 786 ms 58476 KB Output is correct
70 Correct 708 ms 55788 KB Output is correct
71 Correct 697 ms 53724 KB Output is correct
72 Correct 626 ms 54496 KB Output is correct
73 Correct 813 ms 70252 KB Output is correct
74 Correct 639 ms 56136 KB Output is correct