제출 #819299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819299		oneloveforever	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	237 ms	46176 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define ii pair<int,int>
const int inf=1e9+7;
int n,q;
template <typename T>
bool minimize(T &a,T b)
{
    if(a>b)
    {
        a=b;
        return true;
    }
    return false;
}
struct edge
{
    int x,value_x,value_y;
    edge(int _x=0,int _value_x=0,int _value_y=0)
    {
        x=_x,value_x=_value_x,value_y=_value_y;
    }
};
vector<vector<edge> >a;
struct SUB1
{
    int n;
    vector<vector<int> >dp;
    SUB1(int _n=0)
    {
        n=_n;
        dp.resize(n+7,vector<int>(2));
    }
    void dfs(int x,int par)
    {
        dp[x][0]=0;
        dp[x][1]=inf;
        for(edge need:a[x])
        {
            int node=need.x;
            int value_x=need.value_x;
            int value_y=need.value_y;
            if(node==par)continue;
            dfs(node,x);
            dp[x][1]=dp[x][1]+dp[node][0]+value_x;
            minimize(dp[x][1],dp[node][1]+dp[x][0]+value_y);
            dp[x][0]+=dp[node][0]+value_x;
        }
        minimize(dp[x][1],dp[x][0]);
    }
    void calc()
    {
        dfs(1,0);
        cout<<dp[1][1];
    }
};
struct SUB2
{
    int n;
    vector<vector<int> >dp;
    SUB2(int _n=0)
    {
        n=_n;
        dp.resize(n+7,vector<int>(3));
    }
    void dfs(int x,int par)
    {
        dp[x][0]=0;
        dp[x][1]=inf;
        dp[x][2]=inf;
        for(edge need:a[x])
        {
            int node=need.x;
            int value_x=need.value_x;
            int value_y=need.value_y;
            if(node==par)continue;
            dfs(node,x);
            dp[x][2]=dp[x][2]+dp[node][0]+value_x;
            minimize(dp[x][2],dp[node][2]+dp[x][0]+value_y);
            minimize(dp[x][2],dp[node][1]+dp[x][1]);
            dp[x][1]=dp[x][1]+dp[node][0]+value_x;
            minimize(dp[x][1],dp[node][1]+dp[x][0]);
            dp[x][0]+=dp[node][0]+value_x;
        }
        minimize(dp[x][2],dp[x][1]);
        minimize(dp[x][1],dp[x][0]);

    }
    void calc()
    {
        dfs(1,0);
        cout<<dp[1][2]<<endl;
    }
};
struct SUB3
{
    int n,num_node;
    vector<int>dist,fin,beg,trace,par;
    vector<bool>check;
    SUB3(int _n=0)
    {
        n=_n;
        num_node=0;
        dist.resize(n+7);
        fin.resize(n+7);
        beg.resize(n+7);
        check.resize(n+7);
        trace.resize(n+7);
        par.resize(n+7);
    }
    void dfs(int x,int cha)
    {
        beg[x]=++num_node;
        pos[num_node]=x;
        for(edge need:a[x])
        {
            int node=need.x;
            int value_x=need.value_x;
            int value_y=need.value_y;
            if(node==cha)continue;
            par[node]=x;
            dist[node]=dist[x]+value_x;
            trace[node]=value_x;
            dfs(node,x);
        }
        fin[x]=num_node;
    }
    vector<ii>st;
    vector<int> lazy,pos;
    void pre()
    {
        st.resize(4*n+7);
        lazy.resize(4*n+7);
        pos.resize(n+7);
    }
    void down(int id)
    {
        if(!lazy[id])return ;
        st[2*id].x+=lazy[id];
        st[2*id+1].x+=lazy[id];
        lazy[2*id]+=lazy[id];
        lazy[2*id+1]+=lazy[id];
        lazy[id]=0;
    }
    void init(int id,int x,int y)
    {
        if(x==y)
        {
            st[id]=make_pair(dist[pos[x]],pos[x]);
            return ;
        }
        int mid=(x+y)/2;
        init(2*id,x,mid);
        init(2*id+1,mid+1,y);
        st[id]=max(st[2*id],st[2*id+1]);
    }
    void update(int id,int x,int y,int l,int r,int value)
    {
        if(x>r||y<l)return ;
        if(x>=l&&y<=r)
        {
            st[id].x+=value;
            lazy[id]+=value;
            return ;
        }
        down(id);
        int mid=(x+y)/2;
        update(2*id,x,mid,l,r,value);
        update(2*id+1,mid+1,y,l,r,value);
        st[id]=max(st[2*id],st[2*id+1]);
    }
    ii get(int id,int x,int y,int l,int r)
    {
        if(x>r||y<l)return make_pair(-inf,-inf);
        if(x>=l&&y<=r)return st[id];
        down(id);
        int mid=(x+y)/2;
        ii value_x=get(2*id,x,mid,l,r);
        ii value_y=get(2*id+1,mid+1,y,l,r);
        return max(value_x,value_y);
    }

    void change(int x)
    {
        while(check[x])
        {
            check[x]=false;
            update(1,1,n,beg[x],fin[x],-trace[x]);
            x=par[x];
        }
    }
    void calc()
    {
        vector<int>ans(n+1,inf);
        pre();
        for(int i=1; i<=n; i++)
        {
            num_node=0;
            int source=i;
            dist[source]=0;
            dfs(source,0);
            int total=0;
            for(int node=1; node<=n; node++)total+=dist[node];
            minimize(ans[1],total);
            for(int node=1; node<=n; node++)check[node]=true;
            init(1,1,n);
            ii used=get(1,1,n,1,n);
            total-=used.x;
            change(used.y);
            for(int cnt=2; cnt<=n; cnt++)
            {
                used=get(1,1,n,1,n);
                total-=used.x;
                change(used.y);
                minimize(ans[cnt],total);
            }
        }
        int q;
        cin>>q;
        while(q--)
        {
            int x;
            cin>>x;
            cout<<ans[x]<<endl;
        }

    }
};
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    a.resize(n+7);
    for(int i=1; i<=n-1; i++)
    {
        int x,y,value_x,value_y;
        cin>>x>>y>>value_x>>value_y;
        a[x].push_back({y,value_x,value_y});
        a[y].push_back({x,value_y,value_x});
    }
    if(n<=2000)
    {
        SUB3 s(n);
        s.calc();
        return 0;
    }
    int q;
    cin>>q;
    if(q==1)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            SUB1 s(n);
            s.calc();
        }
        if(x==2)
        {
            SUB2 s(n);
            s.calc();
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

designated_cities.cpp: In member function 'void SUB3::dfs(long long int, long long int)':
designated_cities.cpp:122:17: warning: unused variable 'value_y' [-Wunused-variable]
  122 |             int value_y=need.value_y;
      |                 ^~~~~~~

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