oj.uz

Submission #1110011

# Submission time Handle Problem Language Result Execution time Memory
1110011 2024-11-08T12:38:30 Z dwuy Designated Cities (JOI19_designated_cities) C++14
100 / 100
 434 ms 83796 KB 
/**         - 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

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.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 312 ms 54784 KB Output is correct
3 Correct 367 ms 79176 KB Output is correct
4 Correct 333 ms 53316 KB Output is correct
5 Correct 316 ms 54720 KB Output is correct
6 Correct 354 ms 58184 KB Output is correct
7 Correct 310 ms 54900 KB Output is correct
8 Correct 434 ms 79944 KB Output is correct
9 Correct 232 ms 55992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 292 ms 54716 KB Output is correct
3 Correct 366 ms 83528 KB Output is correct
4 Correct 293 ms 53324 KB Output is correct
5 Correct 291 ms 54720 KB Output is correct
6 Correct 282 ms 58736 KB Output is correct
7 Correct 232 ms 55648 KB Output is correct
8 Correct 354 ms 70472 KB Output is correct
9 Correct 229 ms 55480 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14844 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct
13 Correct 6 ms 15356 KB Output is correct
14 Correct 5 ms 15184 KB Output is correct
15 Correct 5 ms 15200 KB Output is correct
16 Correct 5 ms 15184 KB Output is correct
17 Correct 5 ms 15192 KB Output is correct
18 Correct 5 ms 15184 KB Output is correct
19 Correct 5 ms 15352 KB Output is correct
20 Correct 5 ms 15184 KB Output is correct
21 Correct 5 ms 15184 KB Output is correct
22 Correct 5 ms 15188 KB Output is correct
23 Correct 5 ms 15184 KB Output is correct
24 Correct 4 ms 15184 KB Output is correct
25 Correct 5 ms 15440 KB Output is correct
26 Correct 6 ms 15184 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 312 ms 54784 KB Output is correct
3 Correct 367 ms 79176 KB Output is correct
4 Correct 333 ms 53316 KB Output is correct
5 Correct 316 ms 54720 KB Output is correct
6 Correct 354 ms 58184 KB Output is correct
7 Correct 310 ms 54900 KB Output is correct
8 Correct 434 ms 79944 KB Output is correct
9 Correct 232 ms 55992 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 292 ms 54716 KB Output is correct
12 Correct 366 ms 83528 KB Output is correct
13 Correct 293 ms 53324 KB Output is correct
14 Correct 291 ms 54720 KB Output is correct
15 Correct 282 ms 58736 KB Output is correct
16 Correct 232 ms 55648 KB Output is correct
17 Correct 354 ms 70472 KB Output is correct
18 Correct 229 ms 55480 KB Output is correct
19 Correct 4 ms 14672 KB Output is correct
20 Correct 299 ms 54856 KB Output is correct
21 Correct 348 ms 83796 KB Output is correct
22 Correct 277 ms 52976 KB Output is correct
23 Correct 284 ms 53796 KB Output is correct
24 Correct 298 ms 53200 KB Output is correct
25 Correct 294 ms 54740 KB Output is correct
26 Correct 227 ms 53576 KB Output is correct
27 Correct 234 ms 54836 KB Output is correct
28 Correct 219 ms 58268 KB Output is correct
29 Correct 224 ms 54856 KB Output is correct
30 Correct 252 ms 53952 KB Output is correct
31 Correct 234 ms 54972 KB Output is correct
32 Correct 303 ms 71760 KB Output is correct
33 Correct 237 ms 55820 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14844 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 14672 KB Output is correct
13 Correct 312 ms 54784 KB Output is correct
14 Correct 367 ms 79176 KB Output is correct
15 Correct 333 ms 53316 KB Output is correct
16 Correct 316 ms 54720 KB Output is correct
17 Correct 354 ms 58184 KB Output is correct
18 Correct 310 ms 54900 KB Output is correct
19 Correct 434 ms 79944 KB Output is correct
20 Correct 232 ms 55992 KB Output is correct
21 Correct 2 ms 14672 KB Output is correct
22 Correct 292 ms 54716 KB Output is correct
23 Correct 366 ms 83528 KB Output is correct
24 Correct 293 ms 53324 KB Output is correct
25 Correct 291 ms 54720 KB Output is correct
26 Correct 282 ms 58736 KB Output is correct
27 Correct 232 ms 55648 KB Output is correct
28 Correct 354 ms 70472 KB Output is correct
29 Correct 229 ms 55480 KB Output is correct
30 Correct 2 ms 14672 KB Output is correct
31 Correct 6 ms 15356 KB Output is correct
32 Correct 5 ms 15184 KB Output is correct
33 Correct 5 ms 15200 KB Output is correct
34 Correct 5 ms 15184 KB Output is correct
35 Correct 5 ms 15192 KB Output is correct
36 Correct 5 ms 15184 KB Output is correct
37 Correct 5 ms 15352 KB Output is correct
38 Correct 5 ms 15184 KB Output is correct
39 Correct 5 ms 15184 KB Output is correct
40 Correct 5 ms 15188 KB Output is correct
41 Correct 5 ms 15184 KB Output is correct
42 Correct 4 ms 15184 KB Output is correct
43 Correct 5 ms 15440 KB Output is correct
44 Correct 6 ms 15184 KB Output is correct
45 Correct 4 ms 14672 KB Output is correct
46 Correct 299 ms 54856 KB Output is correct
47 Correct 348 ms 83796 KB Output is correct
48 Correct 277 ms 52976 KB Output is correct
49 Correct 284 ms 53796 KB Output is correct
50 Correct 298 ms 53200 KB Output is correct
51 Correct 294 ms 54740 KB Output is correct
52 Correct 227 ms 53576 KB Output is correct
53 Correct 234 ms 54836 KB Output is correct
54 Correct 219 ms 58268 KB Output is correct
55 Correct 224 ms 54856 KB Output is correct
56 Correct 252 ms 53952 KB Output is correct
57 Correct 234 ms 54972 KB Output is correct
58 Correct 303 ms 71760 KB Output is correct
59 Correct 237 ms 55820 KB Output is correct
60 Correct 4 ms 14672 KB Output is correct
61 Correct 286 ms 57416 KB Output is correct
62 Correct 306 ms 80968 KB Output is correct
63 Correct 287 ms 56136 KB Output is correct
64 Correct 268 ms 57604 KB Output is correct
65 Correct 293 ms 56152 KB Output is correct
66 Correct 275 ms 57472 KB Output is correct
67 Correct 284 ms 56404 KB Output is correct
68 Correct 278 ms 57576 KB Output is correct
69 Correct 269 ms 60248 KB Output is correct
70 Correct 258 ms 57416 KB Output is correct
71 Correct 257 ms 56780 KB Output is correct
72 Correct 256 ms 58176 KB Output is correct
73 Correct 289 ms 71496 KB Output is correct
74 Correct 237 ms 60088 KB Output is correct