oj.uz

Submission #819367

# Submission time Handle Problem Language Result Execution time Memory
819367 2023-08-10T09:47:58 Z oneloveforever Designated Cities (JOI19_designated_cities) C++14
16 / 100
 214 ms 39912 KB 
#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;
    int total;
    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;
            total+=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];
        }
    }
    bool check_path(int x,int source)
    {
        while(check[x])
        {
            if(x==source)return true;
            x=par[x];
        }
        return false;
    }
    void calc()
    {
        vector<int>ans(n+1,inf);
        pre();
        for(int i=1; i<=n; i++)
        {
            num_node=0;
            total=0;
            int source=i;
            dist[source]=0;
            trace[source]=0;
            dfs(source,0);
            minimize(ans[1],total);
            for(int j=1;j<=n;j++)check[j]=true;
            init(1,1,n);
            bool ok=true;
            for(int cnt=2; cnt<=n; cnt++)
            {
                ii used=get(1,1,n,1,n);
                total-=used.x;
                change(used.y);
                if(ok)
                {
                    used=get(1,1,n,1,n);
                    if(check_path(used.y,source))
                    {
                        ok=false;
                        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();
        }
    }
}

Compilation message

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

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 158 ms 29004 KB Output is correct
3 Correct 214 ms 38024 KB Output is correct
4 Correct 165 ms 28952 KB Output is correct
5 Correct 162 ms 28548 KB Output is correct
6 Correct 192 ms 30284 KB Output is correct
7 Correct 145 ms 27776 KB Output is correct
8 Correct 167 ms 38480 KB Output is correct
9 Correct 128 ms 26928 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 140 ms 29032 KB Output is correct
3 Correct 184 ms 39912 KB Output is correct
4 Correct 154 ms 28936 KB Output is correct
5 Correct 136 ms 28600 KB Output is correct
6 Correct 164 ms 30544 KB Output is correct
7 Correct 113 ms 27116 KB Output is correct
8 Correct 181 ms 35168 KB Output is correct
9 Correct 103 ms 26872 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 158 ms 29004 KB Output is correct
3 Correct 214 ms 38024 KB Output is correct
4 Correct 165 ms 28952 KB Output is correct
5 Correct 162 ms 28548 KB Output is correct
6 Correct 192 ms 30284 KB Output is correct
7 Correct 145 ms 27776 KB Output is correct
8 Correct 167 ms 38480 KB Output is correct
9 Correct 128 ms 26928 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 140 ms 29032 KB Output is correct
12 Correct 184 ms 39912 KB Output is correct
13 Correct 154 ms 28936 KB Output is correct
14 Correct 136 ms 28600 KB Output is correct
15 Correct 164 ms 30544 KB Output is correct
16 Correct 113 ms 27116 KB Output is correct
17 Correct 181 ms 35168 KB Output is correct
18 Correct 103 ms 26872 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 100 ms 18068 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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