Submission #545964

#	Time	Username	Problem	Language	Result	Execution time	Memory
545964		stefantaga	Training (IOI07_training)	C++14	20 / 100	30 ms	26324 KiB

training

#include <bits/stdc++.h>

using namespace std;
struct NonTreeEdge
{
    int x,y,cost;
};
vector <NonTreeEdge> salut;
vector <int> arb[8005];
int niv[8005];
int fiu[8005],tata[8005];
int rmqTree[8005][14],q,prim[8005];
vector <int> fii[8005];
void dfs(int x,int dad)
{
    int nr=0;
    niv[x]=niv[dad]+1;
    rmqTree[++q][0]=x;
    prim[x]=q;
    for (int i=0;i<arb[x].size();i++)
    {
        int nod = arb[x][i];
        if (nod!=dad)
        {
            tata[nod]=x;
            dfs(nod,x);
            fii[x].push_back(nod);
            fiu[nod]=nr;
            nr++;
            rmqTree[++q][0]=x;
        }
    }
}
int n;
int din[1005][5005];
int i,j,m;
vector <NonTreeEdge> mn[1005];
int lca(int x,int y)
{
    if (x==y)
    {
        return x;
    }
    x=prim[x];
    y=prim[y];
    if (x>y)
    {
        swap(x,y);
    }
    int dif = y-x;
    int k =log2(dif);
    if (niv[rmqTree[x][k]]<niv[rmqTree[y-(1<<k)+1][k]])
    {
        return rmqTree[x][k];
    }
    return rmqTree[y-(1<<k)+1][k];
}
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(q);
    int p  = 1;
    for (int j=1;j<=lg;j++)
    {
        for (i=1;i<=q;i++)
        {
            if (niv[rmqTree[i][j-1]]<niv[rmqTree[i+p][j-1]])
            {
                rmqTree[i][j]=rmqTree[i][j-1];
            }
            else
            {
                rmqTree[i][j]=rmqTree[i+p][j-1];
            }
        }
        p=p*2;
    }
    int lim = (1<<11);
    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]);
    }
    int solutie = lastv-rasp(1,0);
    assert(solutie>0);
    cout<<solutie;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 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