Submission #938906

#	Time	Username	Problem	Language	Result	Execution time	Memory
938906		velislavgarkov	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	469 ms	68912 KiB

designated_cities

#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 (stderr)

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44