Submission #535274

#	Time	Username	Problem	Language	Result	Execution time	Memory
535274		groshi	Railway (BOI17_railway)	C++17	100 / 100	220 ms	23364 KiB

railway

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int poziomy[19][100100];
struct wi{
    vector<int> Q;
    int wiel=0;
    int poz=0;
    int wchodze=0;
    int wynik=0;
    int ktora=0;
    int suma=0;
}*w;
int jestem=1;
void ustaw_poziomy(int x)
{
    for(int i=1;i<19;i++)
        poziomy[i][x]=poziomy[i-1][poziomy[i-1][x]];
}
void dfs(int x,int ojciec)
{
    w[x].wchodze=jestem;
    jestem++;
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pomoc=w[x].Q[i];
        if(pomoc==ojciec)
        {
            w[x].ktora=i;
            continue;
        }
        w[pomoc].poz=w[x].poz+1;
        poziomy[0][pomoc]=x;
        ustaw_poziomy(pomoc);
        dfs(pomoc,x);
    }
}
int nasze_lca(int x,int y)
{
    if(w[x].poz>w[y].poz)
        swap(x,y);
    for(int k=18;k>=0;k--)
        if(w[y].poz-(1<<k)>=w[x].poz)
            y=poziomy[k][y];
    for(int k=18;k>=0;k--)
        if(poziomy[k][x]!=poziomy[k][y])
        {
            x=poziomy[k][x];
            y=poziomy[k][y];
        }
    if(x==y)
        return x;
    return poziomy[0][x];
}
int dfs2(int x,int ojc)
{
    int suma=0;
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
            continue;
        suma+=dfs2(pom,x);
    }
    suma+=w[x].suma;
    w[x].wynik=suma;
    return suma;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,k,x,y;
    cin>>n>>m>>k;
    w=new wi[n+3];
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        w[x].Q.push_back(y);
        w[y].Q.push_back(x);
        w[x].Q.push_back(i);
        w[y].Q.push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int mam;
        cin>>mam;
        vector<pair<int,int> > tak;
        for(int j=0;j<mam;j++)
        {
            cin>>x;
            tak.push_back({w[x].wchodze,x});
        }
        sort(tak.begin(),tak.end());
        for(int j=0;j<tak.size();j++)
        {
            x=tak[j].second;
            y=tak[(j+1)%tak.size()].second;
            int gdzie=nasze_lca(x,y);
            w[x].suma++;
            w[y].suma++;
            w[gdzie].suma-=2;
        }
    }
    int cos=dfs2(1,0);
    vector<int> wypisz;;
    for(int i=2;i<=n;i++)
    {
        if(w[i].wynik>=2*k)
        {
            wypisz.push_back(w[i].Q[w[i].ktora+1]);
        }
    }
    sort(wypisz.begin(),wypisz.end());
    cout<<wypisz.size()<<"\n";
    for(int i=0;i<wypisz.size();i++)
        cout<<wypisz[i]<<" ";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
railway.cpp: In function 'int dfs2(int, int)':
railway.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<tak.size();j++)
      |                     ~^~~~~~~~~~~
railway.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0;i<wypisz.size();i++)
      |                 ~^~~~~~~~~~~~~~
railway.cpp:109:9: warning: unused variable 'cos' [-Wunused-variable]
  109 |     int cos=dfs2(1,0);
      |         ^~~

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