oj.uz

Submission #376472

# Submission time Handle Problem Language Result Execution time Memory
376472 2021-03-11T14:31:49 Z wiwiho Designated Cities (JOI19_designated_cities) C++14
33 / 100
 808 ms 80620 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, ans2;

void dfs1(int now, int p){
    vector<ll> tmp;
    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));
        tmp.eb(dp2[v] + i.get(v));
    }
    gsort(tmp);
    if(tmp.size() >= 2) ans2[now] = tmp[0] + tmp[1];
    else ans2[now] = dp2[now];
}

void dfs2(int now, int p){
    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p){
            ans[now] = ans[p] - i.get(now) + i.get(p);
            continue;
        }
    }
    for(edge i : g[now]){
        int v = i.ano(now);
        if(v == p){
            continue;
        }
        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);
    ans2.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    pr.resize(n + 1);
    pw.resize(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++){
        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)];
        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);
//            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]);
//    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;
}

Subtask #1
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 642 ms 44240 KB Output is correct
3 Correct 695 ms 69612 KB Output is correct
4 Correct 603 ms 44396 KB Output is correct
5 Correct 646 ms 44124 KB Output is correct
6 Correct 699 ms 48312 KB Output is correct
7 Correct 599 ms 43092 KB Output is correct
8 Correct 781 ms 70380 KB Output is correct
9 Correct 593 ms 43976 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 668 ms 44352 KB Output is correct
3 Correct 658 ms 80268 KB Output is correct
4 Correct 665 ms 49236 KB Output is correct
5 Correct 672 ms 50704 KB Output is correct
6 Correct 756 ms 55212 KB Output is correct
7 Correct 612 ms 50148 KB Output is correct
8 Correct 808 ms 67436 KB Output is correct
9 Correct 603 ms 50064 KB Output is correct

Subtask #4
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 642 ms 44240 KB Output is correct
3 Correct 695 ms 69612 KB Output is correct
4 Correct 603 ms 44396 KB Output is correct
5 Correct 646 ms 44124 KB Output is correct
6 Correct 699 ms 48312 KB Output is correct
7 Correct 599 ms 43092 KB Output is correct
8 Correct 781 ms 70380 KB Output is correct
9 Correct 593 ms 43976 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 668 ms 44352 KB Output is correct
12 Correct 658 ms 80268 KB Output is correct
13 Correct 665 ms 49236 KB Output is correct
14 Correct 672 ms 50704 KB Output is correct
15 Correct 756 ms 55212 KB Output is correct
16 Correct 612 ms 50148 KB Output is correct
17 Correct 808 ms 67436 KB Output is correct
18 Correct 603 ms 50064 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 662 ms 50728 KB Output is correct
21 Correct 751 ms 80620 KB Output is correct
22 Correct 606 ms 49388 KB Output is correct
23 Correct 670 ms 51180 KB Output is correct
24 Correct 653 ms 50140 KB Output is correct
25 Correct 712 ms 51252 KB Output is correct
26 Correct 731 ms 49932 KB Output is correct
27 Correct 677 ms 51120 KB Output is correct
28 Correct 678 ms 54636 KB Output is correct
29 Correct 699 ms 51572 KB Output is correct
30 Correct 617 ms 49500 KB Output is correct
31 Correct 592 ms 49376 KB Output is correct
32 Correct 796 ms 68588 KB Output is correct
33 Correct 580 ms 50504 KB Output is correct

Subtask #6
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -