Submission #556115

#	Time	Username	Problem	Language	Result	Execution time	Memory
556115		stefantaga	Railway (BOI17_railway)	C++14	100 / 100	111 ms	24460 KiB

railway

#include <bits/stdc++.h>

using namespace std;
vector <int> v[100005];
int i,n,m,k;
struct wow
{
    int x,y;
} muchie[100005];
int tin[100005],niv[100005],tout[100005];
struct AIB
{
    int aib[400005];
    int ub (int x)
    {
        return x&(-x);
    }
    void update(int poz,int val)
    {
        for (int i=poz; i<=n; i+=ub(i))
        {
            aib[i]+=val;
        }
        return;
    }
    int query(int poz)
    {
        int i,sum=0;
        for (int i=poz; i>=1; i-=ub(i))
        {
            sum+=aib[i];
        }
        return sum;
    }
} V;
int rmq[200005][22];
void precompRMQ()
{
    int i,j;
    for (i=1; i<=19; i++)
    {
        for (j=1; j<=n; j++)
        {
            rmq[j][i]=rmq[rmq[j][i-1]][i-1];
        }
    }
}
int LCA(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return LCA(y,x);
    }
    int dif = niv[x]-niv[y];
    int p=1;
    for (i=0; i<=19; i++)
    {
        if (dif&p)
        {
            x=rmq[x][i];
        }
        p=p*2;
    }
    if (x!=y)
    {
        for (i=19; i>=0; i--)
        {
            if (rmq[x][i]!=rmq[y][i])
            {
                x=rmq[x][i];
                y=rmq[y][i];
            }
        }
        x=rmq[x][0];
    }
    return x;
}
int q=0;
void dfs(int x,int dad)
{
    q++;
    rmq[x][0]=dad;
    niv[x]=niv[dad]+1;
    tin[x]=q;
    for (int i=0; i<v[x].size(); i++)
    {
        int nod = v[x][i];
        if (nod!=dad)
        {
            dfs(nod,x);
        }
    }
    tout[x]=q;
}
bool compare(int a,int b)
{
    return tin[a]>tin[b];
}
int ceau[100005],loc[100005];
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>>k;
    for (i=1; i<=n-1; i++)
    {
        int x,y;
        cin>>muchie[i].x>>muchie[i].y;
        x=muchie[i].x;
        y=muchie[i].y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    precompRMQ();
    for (int teste =1 ; teste <=m ; teste++)
    {
        int nr;
        cin>>nr;
        for (int i=1; i<=nr; i++)
        {
            cin>>ceau[i];
        }
        sort (ceau+1,ceau+nr+1,compare);
        ceau[nr+1]=ceau[1];
        for (int i=1; i<=nr; i++)
        {
            int lca = LCA(ceau[i],ceau[i+1]);
            assert(lca);
            V.update(tin[ceau[i]],1);
            V.update(tin[ceau[i+1]],1);
            V.update(tin[lca],-2);
        }
    }
    for (i=1; i<=n-1; i++)
    {
        if (niv[muchie[i].x]<niv[muchie[i].y])
        {
            loc[muchie[i].y]=i;
        }
        else
        {
            loc[muchie[i].x]=i;
        }
    }
    vector <int> solfin;
    for (i=2; i<=n; i++)
    {
        int val =V.query(tout[i]) - V.query(tin[i]-1);
        if(val>=2*k)
        {
            solfin.push_back(loc[i]);
        }
    }
    sort (solfin.begin(),solfin.end());
    cout<<solfin.size()<<'\n';
    for (i=0; i<solfin.size(); i++)
    {
        cout<<solfin[i]<<" ";
    }
    return 0;
}

Compilation message (stderr)

railway.cpp: In member function 'int AIB::query(int)':
railway.cpp:28:13: warning: unused variable 'i' [-Wunused-variable]
   28 |         int i,sum=0;
      |             ^
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:161:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (i=0; i<solfin.size(); i++)
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25