답안 #545955

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545955 2022-04-05T17:23:49 Z stefantaga Training (IOI07_training) C++14
10 / 100
300 ms 8788 KB
#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

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;
      |             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 724 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 8664 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 2900 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 4564 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 8788 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 4436 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 8660 KB Time limit exceeded
2 Halted 0 ms 0 KB -