oj.uz

Submission #818490

# Submission time Handle Problem Language Result Execution time Memory
818490 2023-08-10T05:06:06 Z oneloveforever Designated Cities (JOI19_designated_cities) C++14
16 / 100
 255 ms 46240 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
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;
    }
};

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});
    }
    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();
        }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 160 ms 30584 KB Output is correct
3 Correct 193 ms 39644 KB Output is correct
4 Correct 148 ms 30460 KB Output is correct
5 Correct 161 ms 30060 KB Output is correct
6 Correct 170 ms 31648 KB Output is correct
7 Correct 185 ms 29152 KB Output is correct
8 Correct 203 ms 39888 KB Output is correct
9 Correct 120 ms 28320 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 221 ms 35420 KB Output is correct
3 Correct 255 ms 46240 KB Output is correct
4 Correct 138 ms 34052 KB Output is correct
5 Correct 147 ms 35096 KB Output is correct
6 Correct 163 ms 36944 KB Output is correct
7 Correct 111 ms 33416 KB Output is correct
8 Correct 186 ms 41504 KB Output is correct
9 Correct 117 ms 33008 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 160 ms 30584 KB Output is correct
3 Correct 193 ms 39644 KB Output is correct
4 Correct 148 ms 30460 KB Output is correct
5 Correct 161 ms 30060 KB Output is correct
6 Correct 170 ms 31648 KB Output is correct
7 Correct 185 ms 29152 KB Output is correct
8 Correct 203 ms 39888 KB Output is correct
9 Correct 120 ms 28320 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 221 ms 35420 KB Output is correct
12 Correct 255 ms 46240 KB Output is correct
13 Correct 138 ms 34052 KB Output is correct
14 Correct 147 ms 35096 KB Output is correct
15 Correct 163 ms 36944 KB Output is correct
16 Correct 111 ms 33416 KB Output is correct
17 Correct 186 ms 41504 KB Output is correct
18 Correct 117 ms 33008 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 105 ms 24420 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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