oj.uz

Submission #1030739

# Submission time Handle Problem Language Result Execution time Memory
1030739 2024-07-22T09:19:33 Z 정희우(#10958) Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 56700 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=200010;
const lint INF=MAX_N*1000000000LL;

struct Edge
{
    int v;
    lint w,wr;
};

struct Seg
{
    int mi;
    lint mx,lazy;
};


int n,q;
vector<Edge> edge[MAX_N];
int sz[MAX_N];
int lock[MAX_N];
int si[MAX_N],ei[MAX_N],vi[MAX_N];
int pa[MAX_N];
lint paw[MAX_N];
Seg seg[MAX_N<<2];
lint ans[MAX_N];

lint getv(int v,int p)
{
    lint ret=0;
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0)
            ret+=e.wr+getv(e.v,v);
    return ret;
}

int fillsz(int v,int p)
{
    sz[v]=1;
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0)
            sz[v]+=fillsz(e.v,v);
    return sz[v];
}

int findc(int v,int p,int half)
{
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0 && sz[e.v]>half)
            return findc(e.v,v,half);
    return v;
}

void dfs(int v,int p,int &i)
{
    vi[i]=v;
    si[v]=i++;
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0)
        {
            pa[e.v]=v;
            paw[e.v]=e.w;
            dfs(e.v,v,i);
        }
    ei[v]=i;
}

void seg_init(int i,int s,int e)
{
    seg[i].mx=seg[i].lazy=0;
    if(s+1==e)
    {
        seg[i].mi=vi[s];
        return;
    }
    seg_init(i<<1,s,(s+e)>>1);
    seg_init(i<<1|1,(s+e)>>1,e);
}

void update_lazy(int i)
{
    seg[i<<1].mx+=seg[i].lazy;
    seg[i<<1].lazy+=seg[i].lazy;
    seg[i<<1|1].mx+=seg[i].lazy;
    seg[i<<1|1].lazy+=seg[i].lazy;
    seg[i].lazy=0;
}

void update_(int i,int s,int e,int l,int r,lint v)
{
    if(s>=r || e<=l)
        return;
    if(l<=s && e<=r)
    {
        seg[i].mx+=v;
        seg[i].lazy+=v;
        return;
    }
    update_lazy(i);
    update_(i<<1,s,(s+e)>>1,l,r,v);
    update_(i<<1|1,(s+e)>>1,e,l,r,v);
    if(seg[i<<1].mx>=seg[i<<1|1].mx)
        seg[i]={seg[i<<1].mi,seg[i<<1].mx,0};
    else
        seg[i]={seg[i<<1|1].mi,seg[i<<1|1].mx,0};
}

int zero(int v,int cn)
{
    if(paw[v]==0)
        return 0;
    update_(1,0,cn,si[v],ei[v],-paw[v]);
    paw[v]=0;
    int r=zero(pa[v],cn);
    return (r) ? r : v;
}

void calc(int v,lint addv)
{
    addv-=getv(v,0);
    fillsz(v,0);
    int cent=findc(v,0,sz[v]/2);
    addv+=getv(cent,0);
    int idx=0;
    paw[cent]=0;
    dfs(cent,0,idx);
    int cn=idx;
    seg_init(1,0,cn);
    for(int i=0;i<cn;i++)
        update_(1,0,cn,si[vi[i]],ei[vi[i]],paw[vi[i]]);
    lint val=addv;
    for(int i=1;i<=cn;i++)
    {
        if(i==2 && seg[1].mx!=0)
        {
            int c1=seg[1].mi;
            val+=seg[1].mx;
            int p=zero(c1,cn);
            update_(1,0,n,si[p],ei[p],-INF);
            int c2=seg[1].mi;
            val+=seg[1].mx;
            update_(1,0,n,si[p],ei[p],INF);
            zero(c2,cn);
        }
        if(i>=3 && seg[1].mx!=0)
        {
            int c=seg[1].mi;
            val+=seg[1].mx;
            zero(c,cn);
        }
        ans[i]=max(ans[i],val);
    }
    lock[cent]=1;
    for(auto e : edge[cent])
        if(lock[e.v]==0)
            calc(e.v,addv+e.w-e.wr);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    lint sum=0;
    for(int i=1;i<n;i++)
    {
        int u,v;lint w,wr;
        cin >> u >> v >> w >> wr;
        edge[u].push_back({v,w,wr});
        edge[v].push_back({u,wr,w});
        sum+=w+wr;
    }
    calc(1,getv(1,0));
    cin >> q;
    while(q--)
    {
        int en;
        cin >> en;
        cout << sum-ans[en] << '\n';
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6948 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1006 ms 44496 KB Output is correct
3 Correct 1882 ms 54752 KB Output is correct
4 Correct 994 ms 43008 KB Output is correct
5 Correct 447 ms 44228 KB Output is correct
6 Correct 1432 ms 45944 KB Output is correct
7 Correct 343 ms 43264 KB Output is correct
8 Execution timed out 2031 ms 55176 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Correct 1203 ms 44600 KB Output is correct
3 Incorrect 1790 ms 56700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6948 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1006 ms 44496 KB Output is correct
3 Correct 1882 ms 54752 KB Output is correct
4 Correct 994 ms 43008 KB Output is correct
5 Correct 447 ms 44228 KB Output is correct
6 Correct 1432 ms 45944 KB Output is correct
7 Correct 343 ms 43264 KB Output is correct
8 Execution timed out 2031 ms 55176 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6948 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Incorrect 3 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -