oj.uz

Submission #862838

# Submission time Handle Problem Language Result Execution time Memory
862838 2023-10-19T05:51:20 Z HuyQuang_re_Zero Training (IOI07_training) C++14
100 / 100
 19 ms 97368 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
vector <int> a[N];
struct edge { int u,v,k; };
vector <edge> c[N],add;
ll n,m,i,u,v,sum,f[N],g[N],p[N],h[N],k,num[N][N],w[11],w2[11][11],dp[N][11][1024],nchild[N];
void dfs(int u)
{
    for(int i=0;i<a[u].size();i++)
    {
        int v=a[u][i];
        if(v!=p[u]) h[v]=h[u]+1,p[v]=u,dfs(v);
    }
}
void opt(ll &a,ll b) { a=max(a,b); }
int LCA(int u,int v)
{
    while(h[u]>h[v]) u=p[u];
    while(h[v]>h[u]) v=p[v];
    while(u!=v) u=p[u],v=p[v];
    return u;
}
int nearest(int u,int v)
{
    while(p[u]!=v) u=p[u];
    return u;
}
ll climb(int u,int v)
{
    ll res=0,last;
    res+=f[u]; last=u; u=p[u];
    while(u!=v)
    {
        res+=dp[u][nchild[u]-1][((1<<nchild[u])-1)^(1<<num[u][last])];
        last=u; u=p[u];
    }
    return res;
}
void DFS(int u)
{
    int i,j,tt;
    for(int i=0;i<a[u].size();i++)
    {
        int v=a[u][i];
        if(v!=p[u]) DFS(v);
    }


    for(int v:a[u])
    {
        if(v!=p[u]) g[nchild[u]]=f[v],num[u][v]=nchild[u]++;
    }
    memset(w,0,sizeof(w));
    memset(w2,0,sizeof(w2));
    for(int i=0;i<c[u].size();i++)
    {
        edge x=c[u][i];
        int v1=x.u,v2=x.v,k=x.k,tg1,tg2;
        ll sum,sum1,sum2;
        if(v2==u)
        {
            tg1=num[u][nearest(v1,u)];
            opt(w[tg1],climb(v1,u)+k);
        }
        else
        {
            tg1=num[u][nearest(v1,u)]; sum1=climb(v1,u);
            tg2=num[u][nearest(v2,u)]; sum2=climb(v2,u);
            opt(w2[tg1][tg2],sum1+sum2+k);
            opt(w2[tg2][tg1],sum1+sum2+k);
        }
    }


    if(nchild[u]==0) return ;
    dp[u][0][0]=0;
    dp[u][0][1]=max(w[0],g[0]);
    for(i=1;i<nchild[u];i++)
    {
        for(tt=0;tt<(1<<i);tt++)
        {
            opt(dp[u][i][tt],dp[u][i-1][tt]);
            opt(dp[u][i][tt|(1<<i)],dp[u][i-1][tt]+max(g[i],w[i]));
            for(j=0;j<i;j++)
                if(BIT(tt,j)==0)
                {
                    opt(dp[u][i][(tt|(1<<i))|(1<<j)],dp[u][i-1][tt]+max(w2[i][j],g[i]+g[j]));
                //    if(u==1 && i==1 && j==0 && tt==0) cerr<<dp[u][1][3]<<'\n';
                }
        }
    }
 //   if(u==1) cerr<<dp[u][1][3];
    f[u]=dp[u][nchild[u]-1][(1<<nchild[u])-1];
}
int main()
{
  //  freopen("training.inp","r",stdin);
    //freopen("training.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    while(m--)
    {
        cin>>u>>v>>k;
        edge tg={ u,v,k };
        if(k==0) a[u].push_back(v),a[v].push_back(u);
        else add.push_back(tg),sum+=k;
    }
    dfs(1);
    for(i=0;i<add.size();i++)
    {
        edge x=add[i];
        int u=x.u,v=x.v,k=x.k,p=LCA(u,v);
        if(h[u]<h[v]) swap(u,v);
        if((h[u]+h[v]-2*h[p])&1) continue;
        edge tg={ u,v,k };
       // cerr<<u<<" "<<v<<" "<<k<<'\n';
        c[p].push_back(tg);
    }
    DFS(1);
    cout<<sum-f[1];
}

Compilation message

training.cpp: In function 'void dfs(int)':
training.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<a[u].size();i++)
      |                 ~^~~~~~~~~~~~
training.cpp: In function 'void DFS(int)':
training.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<a[u].size();i++)
      |                 ~^~~~~~~~~~~~
training.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<c[u].size();i++)
      |                 ~^~~~~~~~~~~~
training.cpp:71:12: warning: unused variable 'sum' [-Wunused-variable]
   71 |         ll sum,sum1,sum2;
      |            ^~~
training.cpp: In function 'int main()':
training.cpp:117:19: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  117 |         edge tg={ u,v,k };
      |                   ^
training.cpp:117:21: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
  117 |         edge tg={ u,v,k };
      |                     ^
training.cpp:117:23: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
  117 |         edge tg={ u,v,k };
      |                       ^
training.cpp:122:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(i=0;i<add.size();i++)
      |             ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96860 KB Output is correct
2 Correct 14 ms 97368 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 53852 KB Output is correct
2 Correct 6 ms 51804 KB Output is correct
3 Correct 6 ms 53816 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 97116 KB Output is correct
2 Correct 11 ms 95320 KB Output is correct
3 Correct 11 ms 95048 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47876 KB Output is correct
2 Correct 8 ms 53772 KB Output is correct
3 Correct 19 ms 97148 KB Output is correct
4 Correct 8 ms 54104 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 97116 KB Output is correct
2 Correct 19 ms 97116 KB Output is correct
3 Correct 14 ms 97116 KB Output is correct
4 Correct 13 ms 95068 KB Output is correct