Submission #545955

#	Time	Username	Problem	Language	Result	Execution time	Memory
545955		stefantaga	Training (IOI07_training)	C++14	10 / 100	1089 ms	8788 KiB

training

#include <bits/stdc++.h>

using namespace std;
struct NonTreeEdge
{
    int x,y,cost;
};
vector <NonTreeEdge> salut;
vector <int> arb[1005];
int niv[1005];
int rmq[1005][12],fiu[1005],tata[1005];
vector <int> fii[1005];
void dfs(int x,int dad)
{
    int nr=0;
    niv[x]=niv[dad]+1;
    for (int i=0;i<arb[x].size();i++)
    {
        int nod = arb[x][i];
        if (nod!=dad)
        {
            tata[nod]=x;
            rmq[nod][0]=x;
            dfs(nod,x);
            fii[x].push_back(nod);
            fiu[nod]=nr;
            nr++;
        }
    }
}
int n;
int lca(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    int dif = niv[x]-niv[y];
    int lg = log2(n);
    for (int i=0;i<=lg;i++)
    {
        if (dif&(1<<i))
        {
            x=rmq[x][i];
        }
    }
    if (x!=y)
    {
        for (int i=lg;i>=1;i--)
        {
            if (rmq[x][i]!=rmq[y][i])
            {
                x=rmq[x][i];
                y=rmq[y][i];
            }
        }
        x=rmq[x][0];
    }
    return x;
}
int din[1005][5005];
int i,j,m;
vector <NonTreeEdge> mn[1005];
int rasp (int rad, int mask)
{
    if (din[rad][mask]!=-1)
    {
        return din[rad][mask];
    }
    int raspfv=0,p=1,nr=0;
    for (int i=0;i<fii[rad].size();i++)
    {
        if ((mask&(1<<i)))
        {
            continue;
        }
        raspfv= raspfv + rasp(fii[rad][i],0);
    }
    din[rad][mask]=raspfv;
    for (int i=0;i<mn[rad].size();i++)
    {
        int x=mn[rad][i].x;
        int y=mn[rad][i].y;
        int cost = mn[rad][i].cost;
        int varf = lca(x,y);
        int copx=x,cop=y;
        int p=1,ok=1;
        for (int j=0;j<fii[rad].size();j++)
        {
            if (mask&p)
            {
                if (lca(x,fii[rad][j])==fii[rad][j]||lca(y,fii[rad][j])==fii[rad][j])
                {
                    ok=0;
                    break;
                }
            }
            p=p*2;
        }
        if (ok==0)
        {
            continue;
        }
        int sum=0;
        varf = lca(x,y);
        if (y==varf)
        {
            swap(x,y);
        }
        if (x==varf)
        {
            sum=sum+rasp(y,0)+cost;
            cop=y;
            while (cop!=x)
            {
                sum=sum+rasp(tata[cop],(1<<fiu[cop]));
                cop=tata[cop];
            }
        }
        else
        {
            sum=sum+rasp(y,0)+rasp(x,0)+cost;
            cop=y;
            while (tata[cop]!=varf)
            {
                sum=sum+rasp(tata[cop],(1<<fiu[cop]));
                cop=tata[cop];
            }
            copx=x;
            while (tata[copx]!=varf)
            {
                sum=sum+rasp(tata[copx],(1<<fiu[copx]));
                copx=tata[copx];
            }
            sum=sum+rasp(varf,(1<<fiu[copx])+(1<<fiu[cop]));
        }
        din[rad][mask]=max(din[rad][mask],sum);
    }
    return din[rad][mask];
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    int lastv=0;
    for (int i=1;i<=m;i++)
    {
        int x,y,tip;
        cin>>x>>y>>tip;
        if (tip==0)
        {
            arb[x].push_back(y);
            arb[y].push_back(x);
        }
        else
        {
            salut.push_back({x,y,tip});
            lastv+=tip;
        }
    }
    dfs(1,0);
    int lg = log2(n);
    for (i=1;i<=lg;i++)
    {
        for (j=1;j<=n;j++)
        {
            rmq[j][i]=rmq[rmq[j][i-1]][i-1];
        }
    }
    int lim = (1<<10);
    for (i=1;i<=n;i++)
    {
        for (j=0;j<lim;j++)
        {
            din[i][j]=-1;
        }
    }
    for (i=0;i<salut.size();i++)
    {
        int x= salut[i].x;
        int y = salut[i].y;
        int ceau  =lca (salut[i].x,salut[i].y);
        if ((niv[salut[i].x]+niv[salut[i].y]-2*niv[ceau])%2==1)
        {
            continue;
        }
        mn[ceau].push_back(salut[i]);
    }
    cout<<lastv-rasp(1,0);
    return 0;
}

Compilation message (stderr)

training.cpp: In function 'void dfs(int, int)':
training.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0;i<arb[x].size();i++)
      |                  ~^~~~~~~~~~~~~~
training.cpp: In function 'int rasp(int, int)':
training.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i=0;i<fii[rad].size();i++)
      |                  ~^~~~~~~~~~~~~~~~
training.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i=0;i<mn[rad].size();i++)
      |                  ~^~~~~~~~~~~~~~~
training.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int j=0;j<fii[rad].size();j++)
      |                      ~^~~~~~~~~~~~~~~~
training.cpp:70:18: warning: unused variable 'p' [-Wunused-variable]
   70 |     int raspfv=0,p=1,nr=0;
      |                  ^
training.cpp:70:22: warning: unused variable 'nr' [-Wunused-variable]
   70 |     int raspfv=0,p=1,nr=0;
      |                      ^~
training.cpp: In function 'int main()':
training.cpp:183:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for (i=0;i<salut.size();i++)
      |              ~^~~~~~~~~~~~~
training.cpp:185:13: warning: unused variable 'x' [-Wunused-variable]
  185 |         int x= salut[i].x;
      |             ^
training.cpp:186:13: warning: unused variable 'y' [-Wunused-variable]
  186 |         int y = salut[i].y;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9