oj.uz

Submission #376495

# Submission time Handle Problem Language Result Execution time Memory
376495 2021-03-11T15:02:49 Z wiwiho Designated Cities (JOI19_designated_cities) C++14
33 / 100
 758 ms 74348 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];
        }
        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:235:12: warning: unused variable 'tmx' [-Wunused-variable]
  235 |         ll tmx = st.mx(), tcnt = 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 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 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 0 ms 364 KB Output is correct
2 Correct 672 ms 44268 KB Output is correct
3 Correct 680 ms 69612 KB Output is correct
4 Correct 592 ms 44268 KB Output is correct
5 Correct 631 ms 44252 KB Output is correct
6 Correct 663 ms 48256 KB Output is correct
7 Correct 602 ms 43092 KB Output is correct
8 Correct 758 ms 70392 KB Output is correct
9 Correct 614 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 647 ms 44256 KB Output is correct
3 Correct 638 ms 73920 KB Output is correct
4 Correct 579 ms 44524 KB Output is correct
5 Correct 680 ms 44252 KB Output is correct
6 Correct 689 ms 48888 KB Output is correct
7 Correct 575 ms 43720 KB Output is correct
8 Correct 753 ms 61164 KB Output is correct
9 Correct 553 ms 44120 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 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 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 0 ms 364 KB Output is correct
2 Correct 672 ms 44268 KB Output is correct
3 Correct 680 ms 69612 KB Output is correct
4 Correct 592 ms 44268 KB Output is correct
5 Correct 631 ms 44252 KB Output is correct
6 Correct 663 ms 48256 KB Output is correct
7 Correct 602 ms 43092 KB Output is correct
8 Correct 758 ms 70392 KB Output is correct
9 Correct 614 ms 44104 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 647 ms 44256 KB Output is correct
12 Correct 638 ms 73920 KB Output is correct
13 Correct 579 ms 44524 KB Output is correct
14 Correct 680 ms 44252 KB Output is correct
15 Correct 689 ms 48888 KB Output is correct
16 Correct 575 ms 43720 KB Output is correct
17 Correct 753 ms 61164 KB Output is correct
18 Correct 553 ms 44120 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 652 ms 44524 KB Output is correct
21 Correct 735 ms 74348 KB Output is correct
22 Correct 594 ms 44396 KB Output is correct
23 Correct 666 ms 44908 KB Output is correct
24 Correct 622 ms 44780 KB Output is correct
25 Correct 637 ms 44796 KB Output is correct
26 Correct 646 ms 44652 KB Output is correct
27 Correct 625 ms 44768 KB Output is correct
28 Correct 674 ms 48092 KB Output is correct
29 Correct 646 ms 45164 KB Output is correct
30 Correct 596 ms 44252 KB Output is correct
31 Correct 584 ms 43092 KB Output is correct
32 Correct 745 ms 62316 KB Output is correct
33 Correct 555 ms 44104 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 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -