Submission #1110011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110011		dwuy	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	434 ms	83796 KiB

designated_cities

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;

struct Edge{
    int u, v, c, d;
    int o(int x){ return u ^ v ^ x; }
    int cost(int st){ return st == u? c : d; }
};

int n;
int p[MX];
int f[MX];
pii d[MX];
Edge edges[MX];
vector<int> G[MX];

void getAll(int u, int p, int &cost){
    for(int i: G[u]){
        int v = edges[i].o(u);
        if(v == p) continue;
        getAll(v, u, cost);
        cost += edges[i].cost(u);
    }
}

void findLL(int u, int p, int cur, pair<int, pii> &best, int &costAll){
    pii b1 = {0, u}, b2 = {OO, 0};
    for(int i: G[u]){
        int v = edges[i].o(u);
        if(v == p) continue;
        findLL(v, u, cur - edges[i].cost(u) + edges[i].cost(v), best, costAll);
        b2 = min(b2, {d[v].fi - edges[i].cost(u), d[v].se});
        if(b1 > b2) swap(b1, b2);
    }
    best = min(best, {costAll + cur + b1.fi + b2.fi, {b1.se, b2.se}});
    f[1] = min(f[1], costAll + cur);
    // cout << u << ' ' << costAll << ' ' << cur << ' ' << b1.fi << endl;
    d[u] = b1;
}

int dfsID = 0;
int num[MX];
int clo[MX];
int r[MX];
void build(int u, int &pre){
    num[u] = ++dfsID;
    for(int i: G[u]){
        int v = edges[i].o(u);
        if(v == p[u]) continue;
        p[v] = u;
        r[v] = r[u] + edges[i].cost(u);
        pre += edges[i].cost(u);
        build(v, pre);
    }
    clo[u] = dfsID;
}

struct Node{
    int lz;
    pii mx;
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n = 0) : n(n), tree(n<<2|3, Node()) {}

    void build(int pos, int fd, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            if(pos <= mid) id = id<<1, hi = mid;
            else lo = mid + 1, id = id<<1 | 1;
        }
        tree[id].mx = {val, fd};
        for(id>>=1; id; id>>=1) tree[id].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
    }

    void down(int id){
        if(tree[id].lz == 0) return;
        int delta = tree[id].lz;
        tree[id<<1].lz += delta;
        tree[id<<1].mx.fi -= delta;
        tree[id<<1|1].lz += delta;
        tree[id<<1|1].mx.fi -= delta;
        tree[id].lz = 0;
    }

    void update(int l, int r, int id, const int &u, const int &v, const int &val){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            tree[id].lz += val;
            tree[id].mx.fi -= val;
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        update(l, mid, id<<1, u, v, val);
        update(mid + 1, r, id<<1|1, u, v, val);
        tree[id].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
    }

    void update(int l, int r, int val){
        update(1, n, 1, l, r, val);
    }
};

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n;
    for(int i=1; i<n; i++){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edges[i] = {u, v, c, d};
        G[u].push_back(i);
        G[v].push_back(i);
    }

    memset(f, 0x3f, sizeof f);
    pair<int, pii> best = {2e18, {0, 0}};
    int costAll = 0;
    getAll(1, 0, costAll);
    findLL(1, 0, 0, best, costAll);


    bitset<MX> homo = 0;
    int L1 = best.se.fi;
    int L2 = best.se.se;
    int pre = 0;
    build(L1, pre);
    homo[L1] = 1;
    SMT smt(n);
    for(int i=1; i<=n; i++) smt.build(num[i], i, r[i]);
    for(int i=2; i<=n; i++){
        int x, u;
        tie(x, u) = smt.tree[1].mx;
        pre -= x;
        f[i] = pre;
        do{
            smt.update(num[u], clo[u], r[u] - r[p[u]]);
            homo[u] = 1;
            u = p[u];
        } while(!homo[u]);
    }

    int q;
    cin >> q;
    while(q--){
        int u; cin >> u;
        cout << f[u] << endl;
    }

    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int32_t main()':
designated_cities.cpp:164:9: warning: unused variable 'L2' [-Wunused-variable]
  164 |     int L2 = best.se.se;
      |         ^~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44