Submission #1096269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096269		trinhvtuan	Railway (BOI17_railway)	C++17	100 / 100	223 ms	140776 KiB

railway

#include <bits/stdc++.h>
using namespace std;
long long c,x,y,z,n,m,k;
int i,j;
long long h[1000001],up[100005][22],f[1000001],q[1000001];
typedef pair<int,int>i2;
vector<i2>a[1000001];
vector<int>pq,e[1000001];
set<int>s[1000001];
bool ok[1000001],ok1[1000001],d[1000001];
void dfs(int u)
{
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        if (v==up[u][0]) continue;
        h[v]=h[u]+1;
        up[v][0]=u;
        for (int j=1;j<=20;j++)
        up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);
    }
}
int lca(int u,int v)
{
    if (h[u]!=h[v])
    {
        if (h[u]<h[v]) swap(u,v);
        int k=(h[u]-h[v]);
        for (int i=0;(1<<i)<=k;i++)
        {
            if (k>>i&1) u=up[u][i];
        }
    }
    if (u==v) return u;
    int k=__lg(h[u]);
    for (int i=k;i>=0;i--)
    {
        if (up[u][i]!=up[v][i])
        {
            u=up[u][i]; v=up[v][i];
        }
    }
    return up[u][0];
}
void dfs1(int u,int pre)
{
    //cout<<u<<" "<<ok[u]<<"\n";
    ok1[u]=ok[u];
    //cout<<u<<" "<<a[u].size()<<"\n";
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        //cout<<u<<" "<<v<<"\n";
        if (v==pre) continue;
        dfs1(v,u);
        //cout<<v<<" "<<ok1[v]<<"\n";
        if (ok1[v]==1)
        {
            d[a[u][i].first]=1;
            //cout<<u<<" "<<v<<"\n";
        }
        ok1[u]=max(ok1[u],ok1[v]);
    }
}
void dfs2(int u,int pre)
{
    for (int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].second;
        if (v==pre) continue;
        dfs2(v,u);
        //if (u==4) cout<<u<<" "<<v<<"\n";
        f[a[u][i].first]=s[v].size();
        if (s[u].size()<s[v].size()) swap(s[u],s[v]);
        for (auto i=s[v].begin();i!=s[v].end();i++)
        {
            s[u].insert(*i);
        }
    }
    //if (u==4) cout<<s[u].size()<<"\n";
    for (int i=0;i<e[u].size();i++)
    {
        auto id=s[u].find(e[u][i]);
        s[u].erase(id);
    }
//    cout<<u<<"\n";
//    for (auto i=s[u].begin();i!=s[u].end();i++)
//    cout<<*i<<" ";
//    cout<<"\n";
}
void sub1()
{
    for (int i=1;i<=m;i++)
    {
        cin>>z;
        for (int j=1;j<=z;j++)
        {
            cin>>q[j]; ok[q[j]]=1;
        }
        dfs1(q[1],0);
        for (int j=1;j<=n;j++)
        {
            if (d[j]==1) f[j]++;
            //cout<<i<<" "<<j<<" "<<d[j]<<" "<<ok[j]<<" "<<ok1[j]<<"\n";
            ok[j]=0; ok1[j]=0; d[j]=0;
        }
        //cout<<"\n";
    }
    for (int i=1;i<=n;i++)
    {
        if (f[i]>=k)
        {
            pq.push_back(i);
        }
    }
    cout<<pq.size()<<"\n";
    for (int i=0;i<pq.size();i++)
    {
        cout<<pq[i]<<" ";
    }
}
void sub2()
{
    for (int i=1;i<=m;i++)
    {
        cin>>z; c=0;
        for (int j=1;j<=z;j++)
        {
            cin>>q[j];
            if (j==1) c=q[j]; else c=lca(c,q[j]);
            s[q[j]].insert(i);
        }
        e[c].push_back(i);
    }
    dfs2(1,0);
    for (int i=1;i<=n;i++)
    {
        if (f[i]>=k) pq.push_back(i);
    }
    cout<<pq.size()<<"\n";
    for (int i=0;i<pq.size();i++)
    cout<<pq[i]<<" ";
}
int main()
{
    //freopen("suaduong.inp", "r" ,stdin);
    //freopen("suaduong.out", "w" ,stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for (int i=1;i<n;i++)
    {
        cin>>x>>y;
        a[x].push_back({i,y});
        a[y].push_back({i,x});
    }
    dfs(1);
    if (n<=5000) sub1(); else
    sub2();
    //cerr<<"time:"<<0.001*clock()<<"\n";
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int)':
railway.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0;i<a[u].size();i++)
      |                  ~^~~~~~~~~~~~
railway.cpp: In function 'void dfs1(int, int)':
railway.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i=0;i<a[u].size();i++)
      |                  ~^~~~~~~~~~~~
railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i=0;i<a[u].size();i++)
      |                  ~^~~~~~~~~~~~
railway.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0;i<e[u].size();i++)
      |                  ~^~~~~~~~~~~~
railway.cpp: In function 'void sub1()':
railway.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i=0;i<pq.size();i++)
      |                  ~^~~~~~~~~~
railway.cpp: In function 'void sub2()':
railway.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i=0;i<pq.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