oj.uz

Submission #862626

# Submission time Handle Problem Language Result Execution time Memory
862626 2023-10-18T16:34:35 Z HuyQuang_re_Zero Training (IOI07_training) C++14
30 / 100
 5 ms 860 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],w[11],w2[11][11],dp[11][1024];
void dfs(int u)
{
    for(int v:a[u])
        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)
{
    u=p[u];
    ll res=0;
    while(u!=v) res+=g[u]-f[u],u=p[u];
    return res;
}
void DFS(int u)
{
    int nchild=0,i,j,tt;
    for(int v:a[u])
        if(v!=p[u])
        {
            DFS(v);
            g[u]+=f[v];
        }
    for(int v:a[u])
        if(v!=p[u]) num[v]=nchild++;
    memset(w,0,sizeof(w));
    memset(w2,0,sizeof(w2));
    memset(dp,0,sizeof(dp));
    for(edge x:c[u])
    {
        int v1=x.u,v2=x.v,k=x.k,tg1,tg2;
        ll sum,sum1,sum2;
        if(v2==u)
        {
            tg1=num[nearest(v1,u)];
            opt(w[tg1],climb(v1,u)+k);
        }
        else
        {
            tg1=num[nearest(v1,u)]; sum1=climb(v1,u);
            tg2=num[nearest(v2,u)]; sum2=climb(v2,u);
            opt(w2[tg1][tg2],sum1+sum2+k);
            opt(w2[tg2][tg1],sum1+sum2+k);
        }
    }
    if(nchild==0) return ;
    dp[0][0]=0;
    dp[0][1]=w[0];
    for(i=1;i<nchild;i++)
    {
        for(tt=0;tt<(1<<i);tt++)
        {
            opt(dp[i][tt],dp[i-1][tt]);
            opt(dp[i][tt|(1<<i)],dp[i-1][tt]+w[i]);
            for(j=0;j<i;j++)
                if(BIT(tt,j)==0)
                    opt(dp[i][(tt|(1<<i))|(1<<j)],dp[i-1][tt]+w2[i][j]);
        }
    }
    ll ma=0;
    for(tt=0;tt<(1<<nchild);tt++) ma=max(ma,dp[nchild-1][tt]);
    f[u]=g[u]+ma;
}
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;
        if(k==0) a[u].push_back(v),a[v].push_back(u);
        else add.push_back({ u,v,k }),sum+=k;
    }
    dfs(1);
    for(edge x:add)
    {
        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;
        c[p].push_back({ u,v,k });
    }
    DFS(1);
    cout<<sum-f[1];
}

Compilation message

training.cpp: In function 'void DFS(int)':
training.cpp:61:12: warning: unused variable 'sum' [-Wunused-variable]
   61 |         ll sum,sum1,sum2;
      |            ^~~
training.cpp: In function 'int main()':
training.cpp:104:30: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  104 |         else add.push_back({ u,v,k }),sum+=k;
      |                              ^
training.cpp:104:32: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
  104 |         else add.push_back({ u,v,k }),sum+=k;
      |                                ^
training.cpp:104:34: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
  104 |         else add.push_back({ u,v,k }),sum+=k;
      |                                  ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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