oj.uz

Submission #938901

# Submission time Handle Problem Language Result Execution time Memory
938901 2024-03-05T19:24:21 Z velislavgarkov Designated Cities (JOI19_designated_cities) C++14
16 / 100
 431 ms 64612 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 <long long, int> 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 8536 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 3 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 1 ms 8536 KB Output is correct
2 Correct 331 ms 46680 KB Output is correct
3 Correct 399 ms 61936 KB Output is correct
4 Correct 290 ms 45272 KB Output is correct
5 Correct 304 ms 46348 KB Output is correct
6 Correct 289 ms 49076 KB Output is correct
7 Correct 316 ms 45488 KB Output is correct
8 Correct 431 ms 62480 KB Output is correct
9 Correct 285 ms 46068 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 332 ms 46712 KB Output is correct
3 Correct 346 ms 64612 KB Output is correct
4 Correct 334 ms 45224 KB Output is correct
5 Correct 316 ms 46360 KB Output is correct
6 Correct 321 ms 49232 KB Output is correct
7 Correct 252 ms 45304 KB Output is correct
8 Correct 371 ms 56724 KB Output is correct
9 Correct 263 ms 44740 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 3 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 1 ms 8536 KB Output is correct
2 Correct 331 ms 46680 KB Output is correct
3 Correct 399 ms 61936 KB Output is correct
4 Correct 290 ms 45272 KB Output is correct
5 Correct 304 ms 46348 KB Output is correct
6 Correct 289 ms 49076 KB Output is correct
7 Correct 316 ms 45488 KB Output is correct
8 Correct 431 ms 62480 KB Output is correct
9 Correct 285 ms 46068 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 332 ms 46712 KB Output is correct
12 Correct 346 ms 64612 KB Output is correct
13 Correct 334 ms 45224 KB Output is correct
14 Correct 316 ms 46360 KB Output is correct
15 Correct 321 ms 49232 KB Output is correct
16 Correct 252 ms 45304 KB Output is correct
17 Correct 371 ms 56724 KB Output is correct
18 Correct 263 ms 44740 KB Output is correct
19 Correct 2 ms 8672 KB Output is correct
20 Incorrect 312 ms 46676 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 8536 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Incorrect 3 ms 12636 KB Output isn't correct
6 Halted 0 ms 0 KB -