oj.uz

Submission #819299

# Submission time Handle Problem Language Result Execution time Memory
819299 2023-08-10T09:05:59 Z oneloveforever Designated Cities (JOI19_designated_cities) C++14
16 / 100
 237 ms 46176 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;
    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();
        }
    }
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 324 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 1 ms 212 KB Output is correct
2 Correct 184 ms 35332 KB Output is correct
3 Correct 171 ms 44384 KB Output is correct
4 Correct 137 ms 34024 KB Output is correct
5 Correct 160 ms 34932 KB Output is correct
6 Correct 166 ms 36624 KB Output is correct
7 Correct 155 ms 34256 KB Output is correct
8 Correct 170 ms 44780 KB Output is correct
9 Correct 145 ms 33432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 144 ms 35424 KB Output is correct
3 Correct 185 ms 46176 KB Output is correct
4 Correct 161 ms 34052 KB Output is correct
5 Correct 146 ms 35016 KB Output is correct
6 Correct 164 ms 37024 KB Output is correct
7 Correct 115 ms 33296 KB Output is correct
8 Correct 237 ms 41396 KB Output is correct
9 Correct 105 ms 33012 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 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 184 ms 35332 KB Output is correct
3 Correct 171 ms 44384 KB Output is correct
4 Correct 137 ms 34024 KB Output is correct
5 Correct 160 ms 34932 KB Output is correct
6 Correct 166 ms 36624 KB Output is correct
7 Correct 155 ms 34256 KB Output is correct
8 Correct 170 ms 44780 KB Output is correct
9 Correct 145 ms 33432 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 144 ms 35424 KB Output is correct
12 Correct 185 ms 46176 KB Output is correct
13 Correct 161 ms 34052 KB Output is correct
14 Correct 146 ms 35016 KB Output is correct
15 Correct 164 ms 37024 KB Output is correct
16 Correct 115 ms 33296 KB Output is correct
17 Correct 237 ms 41396 KB Output is correct
18 Correct 105 ms 33012 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 110 ms 24440 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 324 KB Output isn't correct
3 Halted 0 ms 0 KB -