oj.uz

Submission #938904

# Submission time Handle Problem Language Result Execution time Memory
938904 2024-03-05T19:26:13 Z velislavgarkov Designated Cities (JOI19_designated_cities) C++14
16 / 100
 501 ms 57684 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;
    int 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 2 ms 12636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 343 ms 39836 KB Output is correct
3 Correct 404 ms 55124 KB Output is correct
4 Correct 401 ms 39876 KB Output is correct
5 Correct 387 ms 39664 KB Output is correct
6 Correct 337 ms 42068 KB Output is correct
7 Correct 310 ms 38680 KB Output is correct
8 Correct 501 ms 55888 KB Output is correct
9 Correct 270 ms 37748 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 419 ms 39788 KB Output is correct
3 Correct 413 ms 57684 KB Output is correct
4 Correct 451 ms 39712 KB Output is correct
5 Correct 368 ms 39660 KB Output is correct
6 Correct 292 ms 42640 KB Output is correct
7 Correct 281 ms 38136 KB Output is correct
8 Correct 447 ms 50076 KB Output is correct
9 Correct 235 ms 37588 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 2 ms 12636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 343 ms 39836 KB Output is correct
3 Correct 404 ms 55124 KB Output is correct
4 Correct 401 ms 39876 KB Output is correct
5 Correct 387 ms 39664 KB Output is correct
6 Correct 337 ms 42068 KB Output is correct
7 Correct 310 ms 38680 KB Output is correct
8 Correct 501 ms 55888 KB Output is correct
9 Correct 270 ms 37748 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 419 ms 39788 KB Output is correct
12 Correct 413 ms 57684 KB Output is correct
13 Correct 451 ms 39712 KB Output is correct
14 Correct 368 ms 39660 KB Output is correct
15 Correct 292 ms 42640 KB Output is correct
16 Correct 281 ms 38136 KB Output is correct
17 Correct 447 ms 50076 KB Output is correct
18 Correct 235 ms 37588 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Incorrect 363 ms 39748 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 2 ms 12636 KB Output isn't correct
6 Halted 0 ms 0 KB -