oj.uz

Submission #376494

# Submission time Handle Problem Language Result Execution time Memory
376494 2021-03-11T15:01:47 Z wiwiho Designated Cities (JOI19_designated_cities) C++14
33 / 100
 750 ms 74092 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)];
        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];
        }
        assert(tcnt == tmx);
        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]);
//    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 0 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 Incorrect 0 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 0 ms 364 KB Output is correct
2 Correct 665 ms 44268 KB Output is correct
3 Correct 662 ms 69612 KB Output is correct
4 Correct 581 ms 44400 KB Output is correct
5 Correct 610 ms 44124 KB Output is correct
6 Correct 679 ms 48236 KB Output is correct
7 Correct 593 ms 43076 KB Output is correct
8 Correct 744 ms 70380 KB Output is correct
9 Correct 558 ms 44104 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 622 ms 44224 KB Output is correct
3 Correct 632 ms 74092 KB Output is correct
4 Correct 639 ms 44268 KB Output is correct
5 Correct 647 ms 44252 KB Output is correct
6 Correct 664 ms 49132 KB Output is correct
7 Correct 586 ms 43976 KB Output is correct
8 Correct 750 ms 61036 KB Output is correct
9 Correct 587 ms 43980 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 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 0 ms 364 KB Output is correct
2 Correct 665 ms 44268 KB Output is correct
3 Correct 662 ms 69612 KB Output is correct
4 Correct 581 ms 44400 KB Output is correct
5 Correct 610 ms 44124 KB Output is correct
6 Correct 679 ms 48236 KB Output is correct
7 Correct 593 ms 43076 KB Output is correct
8 Correct 744 ms 70380 KB Output is correct
9 Correct 558 ms 44104 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 622 ms 44224 KB Output is correct
12 Correct 632 ms 74092 KB Output is correct
13 Correct 639 ms 44268 KB Output is correct
14 Correct 647 ms 44252 KB Output is correct
15 Correct 664 ms 49132 KB Output is correct
16 Correct 586 ms 43976 KB Output is correct
17 Correct 750 ms 61036 KB Output is correct
18 Correct 587 ms 43980 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 637 ms 44268 KB Output is correct
21 Correct 716 ms 74088 KB Output is correct
22 Correct 578 ms 44524 KB Output is correct
23 Correct 670 ms 44780 KB Output is correct
24 Correct 626 ms 44908 KB Output is correct
25 Correct 637 ms 44824 KB Output is correct
26 Correct 645 ms 44672 KB Output is correct
27 Correct 604 ms 44772 KB Output is correct
28 Correct 656 ms 48236 KB Output is correct
29 Correct 630 ms 45164 KB Output is correct
30 Correct 579 ms 44128 KB Output is correct
31 Correct 580 ms 42964 KB Output is correct
32 Correct 737 ms 62444 KB Output is correct
33 Correct 549 ms 43976 KB Output is correct

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -