oj.uz

Submission #938906

# Submission time Handle Problem Language Result Execution time Memory
938906 2024-03-05T19:28:44 Z velislavgarkov Designated Cities (JOI19_designated_cities) C++14
100 / 100
 469 ms 68912 KB 
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=2e5+10;
#define endl '\n'
struct Edge {
    int to;
    long long pl, op;
};
struct Node {
    long long mx;
    int idx;
    long long lazy;
};
Node tree[4*MAXN];
vector <Edge> v[MAXN];
pair <int, long long> par[MAXN];
long long one[MAXN], maxpath1[MAXN], maxpath2[MAXN];
long long ans[MAXN];
int vr1[MAXN], vr2[MAXN];
int in[MAXN], maxin[MAXN], idx[MAXN], cnt;
bool used[MAXN];
long long sumall, sum;
int n;
void get_sum(int x, int p) {
    for (auto i:v[x]) {
        if (i.to==p) continue;
        sum+=i.op;
        get_sum(i.to,x);
    }
}
void find_one(int x, int p, long long cur_sum) {
    one[x]=cur_sum;
    ans[1]=max(ans[1],one[x]);
    for (auto i:v[x]) {
        if (i.to==p) continue;
        find_one(i.to,x,cur_sum+i.pl-i.op);
    }
}
void find_two(int x, int p) {
    if (v[x].size()==1) maxpath1[x]=maxpath2[x]=one[x];
    else maxpath1[x]=maxpath2[x]=0;
    vr1[x]=vr2[x]=x;
    for (auto i:v[x]) {
        if (i.to==p) continue;
        find_two(i.to,x);
        long long s=i.pl+i.op;
        if (maxpath1[i.to]+s>maxpath1[x]) {
            maxpath2[x]=maxpath1[x];
            vr2[x]=vr1[x];
            maxpath1[x]=maxpath1[i.to]+s;
            vr1[x]=vr1[i.to];
        } else if (maxpath1[i.to]+s>maxpath2[x]) {
            maxpath2[x]=maxpath1[i.to]+s;
            vr2[x]=vr1[i.to];
        }
    }
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node].idx=l;
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node].idx=tree[node*2].idx;
}
void push_lazy(int node, int l, int r) {
    if (tree[node].lazy==0) return;
    tree[node].mx+=tree[node].lazy;
    if (l!=r) {
        tree[node*2].lazy+=tree[node].lazy;
        tree[node*2+1].lazy+=tree[node].lazy;
    }
    tree[node].lazy=0;
}
void update(int node, int l, int r, int ql, int qr, long long ch) {
    push_lazy(node,l,r);
    if (ql>r || qr<l) return;
    if (l>=ql && r<=qr) {
        tree[node].lazy+=ch;
        push_lazy(node,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr,ch);
    update(node*2+1,mid+1,r,ql,qr,ch);
    if (tree[node*2].mx>tree[node*2+1].mx) {
        tree[node].mx=tree[node*2].mx;
        tree[node].idx=tree[node*2].idx;
    } else {
        tree[node].mx=tree[node*2+1].mx;
        tree[node].idx=tree[node*2+1].idx;
    }
}
void precomp_dfs(int x, int p) {
    cnt++;
    in[x]=maxin[x]=cnt;
    idx[cnt]=x;
    for (auto i:v[x]) {
        if (i.to==p) continue;
        par[i.to]={x,i.pl};
        precomp_dfs(i.to,x);
        update(1,1,n,in[i.to],maxin[i.to],i.pl);
        maxin[x]=maxin[i.to];
    }
}
void update_path(int x) {
    while (true) {
        if (par[x].first==-1 || used[x]) return;
        used[x]=true;
        update(1,1,n,in[x],maxin[x],-par[x].second);
        x=par[x].first;
    }
}
void solve() {
    if (n==2) {
        ans[1]=max(v[1][0].pl,v[1][0].op);
        ans[2]=v[1][0].pl+v[1][0].op;
        return;
    }
    get_sum(1,-1);
    find_one(1,-1,sum);
    int root=-1;
    for (int i=1;i<=n;i++) {
        if (v[i].size()>1) {
            root=i;
            break;
        }
    }
    find_two(root,-1);
    int s1, s2;
    for (int i=1;i<=n;i++) {
        if (v[i].size()>1 && maxpath2[i]>0 && (maxpath1[i]+maxpath2[i])/2>ans[2]) {
            ans[2]=(maxpath1[i]+maxpath2[i])/2;
            s1=vr1[i];
            s2=vr2[i];
            root=i;
        }
    }
    build_tree(1,1,n);
    par[root]={-1,-1};
    precomp_dfs(root,-1);
    update_path(s1);
    update_path(s2);
    for (int i=3;i<=n;i++) {
        int x=idx[tree[1].idx];
        ans[i]=ans[i-1]+tree[1].mx;
        if (tree[1].mx==0) continue;
        update_path(x);
    }
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    long long c, d;
    cin >> n;
    for (int i=0;i<n-1;i++) {
        cin >> a >> b >> c >> d;
        v[a].push_back({b,c,d});
        v[b].push_back({a,d,c});
        sumall+=c+d;
    }
    solve();
    int q;
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> a;
        cout << sumall-ans[a] << endl;
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:146:16: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |     update_path(s2);
      |     ~~~~~~~~~~~^~~~
designated_cities.cpp:145:16: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |     update_path(s1);
      |     ~~~~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 360 ms 44352 KB Output is correct
3 Correct 405 ms 59856 KB Output is correct
4 Correct 324 ms 44372 KB Output is correct
5 Correct 355 ms 44268 KB Output is correct
6 Correct 368 ms 46676 KB Output is correct
7 Correct 312 ms 43464 KB Output is correct
8 Correct 417 ms 60128 KB Output is correct
9 Correct 253 ms 43764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 347 ms 44464 KB Output is correct
3 Correct 370 ms 62588 KB Output is correct
4 Correct 311 ms 44360 KB Output is correct
5 Correct 327 ms 44092 KB Output is correct
6 Correct 362 ms 46920 KB Output is correct
7 Correct 270 ms 43564 KB Output is correct
8 Correct 407 ms 54552 KB Output is correct
9 Correct 259 ms 43508 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 5 ms 13148 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct
16 Correct 5 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 5 ms 12892 KB Output is correct
20 Correct 4 ms 12888 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12892 KB Output is correct
23 Correct 5 ms 12892 KB Output is correct
24 Correct 5 ms 12892 KB Output is correct
25 Correct 5 ms 13124 KB Output is correct
26 Correct 4 ms 13028 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 360 ms 44352 KB Output is correct
3 Correct 405 ms 59856 KB Output is correct
4 Correct 324 ms 44372 KB Output is correct
5 Correct 355 ms 44268 KB Output is correct
6 Correct 368 ms 46676 KB Output is correct
7 Correct 312 ms 43464 KB Output is correct
8 Correct 417 ms 60128 KB Output is correct
9 Correct 253 ms 43764 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 347 ms 44464 KB Output is correct
12 Correct 370 ms 62588 KB Output is correct
13 Correct 311 ms 44360 KB Output is correct
14 Correct 327 ms 44092 KB Output is correct
15 Correct 362 ms 46920 KB Output is correct
16 Correct 270 ms 43564 KB Output is correct
17 Correct 407 ms 54552 KB Output is correct
18 Correct 259 ms 43508 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 346 ms 44328 KB Output is correct
21 Correct 452 ms 68912 KB Output is correct
22 Correct 322 ms 49376 KB Output is correct
23 Correct 357 ms 51284 KB Output is correct
24 Correct 345 ms 49972 KB Output is correct
25 Correct 368 ms 51028 KB Output is correct
26 Correct 344 ms 49748 KB Output is correct
27 Correct 340 ms 50636 KB Output is correct
28 Correct 368 ms 52564 KB Output is correct
29 Correct 354 ms 51364 KB Output is correct
30 Correct 327 ms 49416 KB Output is correct
31 Correct 298 ms 49408 KB Output is correct
32 Correct 469 ms 61476 KB Output is correct
33 Correct 281 ms 50080 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 360 ms 44352 KB Output is correct
14 Correct 405 ms 59856 KB Output is correct
15 Correct 324 ms 44372 KB Output is correct
16 Correct 355 ms 44268 KB Output is correct
17 Correct 368 ms 46676 KB Output is correct
18 Correct 312 ms 43464 KB Output is correct
19 Correct 417 ms 60128 KB Output is correct
20 Correct 253 ms 43764 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 347 ms 44464 KB Output is correct
23 Correct 370 ms 62588 KB Output is correct
24 Correct 311 ms 44360 KB Output is correct
25 Correct 327 ms 44092 KB Output is correct
26 Correct 362 ms 46920 KB Output is correct
27 Correct 270 ms 43564 KB Output is correct
28 Correct 407 ms 54552 KB Output is correct
29 Correct 259 ms 43508 KB Output is correct
30 Correct 2 ms 8540 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 5 ms 13148 KB Output is correct
33 Correct 4 ms 12892 KB Output is correct
34 Correct 5 ms 12892 KB Output is correct
35 Correct 4 ms 12892 KB Output is correct
36 Correct 4 ms 12892 KB Output is correct
37 Correct 5 ms 12892 KB Output is correct
38 Correct 4 ms 12888 KB Output is correct
39 Correct 4 ms 12892 KB Output is correct
40 Correct 4 ms 12892 KB Output is correct
41 Correct 5 ms 12892 KB Output is correct
42 Correct 5 ms 12892 KB Output is correct
43 Correct 5 ms 13124 KB Output is correct
44 Correct 4 ms 13028 KB Output is correct
45 Correct 2 ms 8540 KB Output is correct
46 Correct 346 ms 44328 KB Output is correct
47 Correct 452 ms 68912 KB Output is correct
48 Correct 322 ms 49376 KB Output is correct
49 Correct 357 ms 51284 KB Output is correct
50 Correct 345 ms 49972 KB Output is correct
51 Correct 368 ms 51028 KB Output is correct
52 Correct 344 ms 49748 KB Output is correct
53 Correct 340 ms 50636 KB Output is correct
54 Correct 368 ms 52564 KB Output is correct
55 Correct 354 ms 51364 KB Output is correct
56 Correct 327 ms 49416 KB Output is correct
57 Correct 298 ms 49408 KB Output is correct
58 Correct 469 ms 61476 KB Output is correct
59 Correct 281 ms 50080 KB Output is correct
60 Correct 2 ms 8536 KB Output is correct
61 Correct 373 ms 53344 KB Output is correct
62 Correct 395 ms 67920 KB Output is correct
63 Correct 340 ms 52072 KB Output is correct
64 Correct 384 ms 53724 KB Output is correct
65 Correct 379 ms 52564 KB Output is correct
66 Correct 379 ms 53844 KB Output is correct
67 Correct 397 ms 52704 KB Output is correct
68 Correct 368 ms 53516 KB Output is correct
69 Correct 396 ms 55564 KB Output is correct
70 Correct 384 ms 53960 KB Output is correct
71 Correct 345 ms 52236 KB Output is correct
72 Correct 314 ms 52728 KB Output is correct
73 Correct 440 ms 62292 KB Output is correct
74 Correct 301 ms 53792 KB Output is correct