Submission #165071

#	Time	Username	Problem	Language	Result	Execution time	Memory
165071		puppies_and_rainbows	Designated Cities (JOI19_designated_cities)	C++14	56 / 100	2023 ms	65284 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
using namespace std;

int sum=0, m, n;
int u[200005], v[200005], a[200005],b[200005];
int tin[200005], tout[200005], pos[200005];
vector<int> adj[200005];
int ans[200005];
bool used[200005];
pair<int, int> trace2;

int f[200005];
int lazy[800005];
pair<int, int> it[800005];

int now=0, dora;

void down(int id){
    it[id*2].first+=lazy[id];
    it[id*2+1].first+=lazy[id];
    lazy[id*2]+=lazy[id];
    lazy[id*2+1]+=lazy[id];
    lazy[id]=0;
}
void update(int id, int l, int r, int u, int v, int val){
    if(l>v||r<u) return;
    if(l>=u&&r<=v)
    {
        it[id].first+=val;
        lazy[id]+=val;
        return;
    }
    down(id);
    int mid=(l+r)/2;
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    it[id]=max(it[id*2], it[id*2+1]);
}
pair<int, int> get(int id, int l, int r, int u, int v){
    if(l>v||r<u) return{-1, -1};
    if(l>=u&&r<=v)
    {
        return it[id];
    }
    down(id);
    int mid=(l+r)/2;
    return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
pair<int, int> unpack(int node, int i){
    int uv=a[i], vu=b[i];
    if(node!=u[i])
    {
        swap(uv, vu);
    }
    return {uv, vu};
}
void dfs(int node, int fa){
    f[node]=fa;
    dora++;
    tin[node]=dora;
    pos[dora]=node;
    for(auto i:adj[node])
    {
        int other=u[i]+v[i]-node, uv, vu;
        if(other==fa) continue;
        tie(uv, vu)=unpack(node, i);
        dfs(other, node);
    }
    tout[node]=dora;
    for(auto i:adj[node])
    {
        int other=u[i]+v[i]-node, uv, vu;
        if(other==fa) continue;
        tie(uv, vu)=unpack(node, i);
        update(1, 1, n, tin[other], tout[other], uv);
        now+=vu;
    }
}
void dfsget(int node, int fa){
    int w, oth;
    ans[1]=max(ans[1], now);
    tie(w, oth)=it[1];
    if(ans[2]<w+now)
    {
    	// cout<<w<<" "<<now<<endl;
        ans[2]=w+now;
        trace2={node, oth};
    }
    for(auto i:adj[node])
    {
        int other=u[i]+v[i]-node, uv, vu;
        if(other==fa) continue;
        tie(uv, vu)=unpack(node, i);
        now+=uv-vu;
        update(1, 1, n, 1, n, vu);
        update(1, 1, n, tin[other], tout[other], -vu-uv);
        dfsget(other, node);
        now-=uv-vu;
        update(1, 1, n, 1, n, -vu);
        update(1, 1, n, tin[other], tout[other], +vu+uv);
    }
}
void rebuild(int id, int l, int r){
    if(l==r)
    {
    	it[id]={0, pos[l]};
    	lazy[id]=0;
    }
    else
    {
        int mid=(l+r)/2;
        rebuild(id*2, l, mid);
        rebuild(id*2+1, mid+1, r);
        it[id]=min(it[id*2], it[id*2+1]);
        lazy[id]=0;
    }
}

signed main()
{
	ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<n; i++)
    {
        cin>>u[i]>>v[i]>>a[i]>>b[i];
        sum+=a[i]+b[i];
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    dora=0, now=0;
    dfs(1, 1);
    rebuild(1, 1, n);
    dora=0, now=0;
    dfs(1, 1);
    dfsget(1, 1);
    // cout<<"wow shit this happened"<<endl;
    dora=0, now=0;
    dfs(trace2.first, trace2.first);
    rebuild(1, 1, n);
    dora=0, now=0;
    dfs(trace2.first, trace2.first);
    int lfcnt=0;
    for(int i=1; i<=n; i++)
    {
        if(adj[i].size()==1)
        {
            lfcnt++;
        }
    }
    used[trace2.first]=true;
    // for(int i=1; i<=4; i++)
    // {
    // 	cout<<f[i]<<endl;
    // }
    // return 0;
    for(int i=2; i<=lfcnt; i++)
    {
    	ans[i]=ans[i-1];
    	if(i==2) ans[i]=now;
        int w, oth;
        tie(w, oth)=it[1];
        while(!used[oth])
        {
        	// cout<<oth<<endl;
            for(auto j:adj[oth])
            {
                if(u[j]+v[j]-oth==f[oth])
                {
                    int uv, vu;
                    tie(uv, vu)=unpack(oth, j);
                    update(1, 1, n, tin[oth], tout[oth], -vu);
                    ans[i]+=vu;
                    used[oth]=true;
                    break;
                }
            }
            oth=f[oth];
        }
    }
    // cout<<"how the fuck did my code even run to this point"<<endl;
    int q;
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        int ax;
        cin>>ax;
        if(ax>lfcnt) ax=lfcnt;
        cout<<sum-ans[ax]<<'\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 0 / 44