oj.uz

Submission #1030557

# Submission time Handle Problem Language Result Execution time Memory
1030557 2024-07-22T06:50:23 Z MMihalev Training (IOI07_training) C++14
100 / 100
 14 ms 8796 KB 
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
#include<unordered_map>
using namespace std;
const int MAX_N=1e3+3;
const int MAX_M=5e3+3;
const int MASK=(1<<10);
const int LOG=10;
int calc[MAX_N][MAX_N];
int dp[MAX_N][MASK];
int idx[MAX_M];
int pointspath[MAX_M][2][2];
int cost[MAX_M];
vector<int>edges[MAX_N];
vector<int>g[MAX_N];
int par[MAX_N][LOG];
int endss[MAX_M][2];
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
int d[MAX_N];
int T;
int n,m;
int sumedges;
void dfs(int u)
{
    in[u]=++T;
    ver[T]=u;
    int sz=0;
    for(int v:g[u])
    {
        if(v==par[u][0])continue;
        par[v][0]=u;
        d[v]=d[u]+1;
        idx[v]=sz++;
        dfs(v);
    }
    out[u]=T;
}
int lca(int u,int v)
{
    if(d[u]>d[v])swap(u,v);
    for(int j=LOG-1;j>=0;j--)
    {
        if(d[v]-(1<<j)>=d[u])
        {
            v=par[v][j];
        }
    }
    if(u==v)return u;
    for(int j=LOG-1;j>=0;j--)
    {
        if(par[v][j]!=par[u][j])
        {
            v=par[v][j];
            u=par[u][j];
        }
    }
    return par[u][0];
}
void precompute()
{
    dfs(1);

    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i<=n;i++)
        {
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=m;i++)
    {
        if(!cost[i])continue;

        int u=endss[i][0],v=endss[i][1];
        int LCA=lca(u,v);

        if((d[u]+d[v]-2*d[LCA])%2==1)continue;

        edges[LCA].push_back(i);

        pointspath[i][0][0]=u;
        while(u!=LCA && par[u][0]!=LCA)u=par[u][0];
        pointspath[i][0][1]=u;

        pointspath[i][1][0]=v;
        while(v!=LCA && par[v][0]!=LCA)v=par[v][0];
        pointspath[i][1][1]=v;
    }
}
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        sumedges+=c;
        cost[i]=c;
        if(c==0)
        {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        else
        {
            endss[i][0]=u;
            endss[i][1]=v;
        }
    }
}
void DFS(int u)
{
    for(int v:g[u])
    {
        if(v==par[u][0])continue;
        DFS(v);
    }

    int sz=g[u].size()-(par[u][0]!=0);

    for(int mask=1;mask<(1<<sz);mask++)
    {
        for(int v:g[u])
        {
            if(v==par[u][0])continue;
            if(((1<<idx[v])&mask)!=0)dp[u][mask]+=dp[v][(1<<(g[v].size()-1))-1];
        }///do not use even edge

        for(int edge:edges[u])
        {
            int cur=0,nmask=mask;
            bool val=1;
            for(int f=0;f<2;f++)
            {
                if(pointspath[edge][f][1]!=u)
                {
                    if(((1<<idx[pointspath[edge][f][1]])&mask)==0)val=0;

                    nmask&= ~(1<<idx[pointspath[edge][f][1]]);
                }

                cur+=calc[pointspath[edge][f][0]][pointspath[edge][f][1]];
            }
            cur+=dp[u][nmask];

            if(val)dp[u][mask]=max(dp[u][mask],cur+cost[edge]);
        }///use even edge
    }

    for(int v:g[u])
    {
        if(v==par[u][0])continue;

        for(int pos=in[v];pos<=out[v];pos++)
        {
            int vert=ver[pos];

            calc[vert][u]=calc[vert][v]+dp[u][((1<<sz)-1) & ~(1<<idx[v])];
        }
    }

    calc[u][u]=dp[u][(1<<sz)-1];
}
void solve()
{
    DFS(1);
    int ans=sumedges-dp[1][(1<<(g[1].size()))-1];
    cout<<ans<<"\n";
}
signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    precompute();
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8796 KB Output is correct
2 Correct 5 ms 8792 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 6 ms 4496 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 10 ms 7032 KB Output is correct
3 Correct 4 ms 7004 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 14 ms 8540 KB Output is correct
4 Correct 3 ms 4524 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7516 KB Output is correct
2 Correct 10 ms 8704 KB Output is correct
3 Correct 8 ms 7260 KB Output is correct
4 Correct 11 ms 7512 KB Output is correct