Submission #1084655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084655		tien9d2	Railway (BOI17_railway)	C++14	100 / 100	95 ms	39996 KiB

railway

#include<bits/stdc++.h>
#define ll pair<int,int>
using namespace std;

const int N=100022;
int n2=0;
int rmq[N*2][20];
int lg2[N*2];
int vt[N];
int h[N];
vector<int> ke[N];
vector<int> ke2[N];
int gt[N],gt2[N];
vector<int> kq;
int n,m,k;
int cal[N];

int getlca(int u,int v)
{
    int l=vt[u];
    int r=vt[v];
    if (l>r) swap(l,r);
    int leng2=lg2[r-l+1];
    int kk=rmq[l][leng2];
    int kkk=rmq[r-(1<<leng2)+1][leng2];
    return (h[kk]<h[kkk] ? kk : kkk);
}

void dfs(int u,int pa)
{
    n2++;
    rmq[n2][0]=u;
    lg2[n2]=log2(n2);
    vt[u]=n2;
    for (int i=0;i<ke[u].size();i++)
    {
        int v=ke[u][i];
        if (v==pa) continue;
        h[v]=h[u]+1;
        dfs(v,u);
        n2++;
        rmq[n2][0]=u;
        lg2[n2]=log2(n2);
    }
}

void dfs3(int u,int pa)
{
    for (int i=0;i<ke[u].size();i++)
    {
        int v=ke[u][i];
        if (v==pa) continue;
        dfs3(v,u);
        gt[u]+=gt[v];
    }
    //cout << gt[u] << " " << u << '\n';
    if (gt[u]>=k) kq.push_back(u);
    gt[u]+=gt2[u];
}

bool cmp(int a,int b)
{
    return vt[a]<vt[b];
}

void dfs2(int u,int pa)
{
    for (int i=0;i<ke2[u].size();i++)
    {
        int v=ke2[u][i];
        if (v==pa) continue;
        dfs2(v,u);
        gt[v]++;
        gt[u]--;
    }
}

bool cmp2(int a,int b)
{
    return cal[a]<cal[b];
}

signed main()
{
    // freopen("army.inp","r",stdin);
    // freopen("army.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    vector<ll> canh;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
        canh.push_back({u,v});
    }
    dfs(1,0);
    for (int i=1;i<=log2(n2);i++)
    {
        for (int i2=1;i2<=n2-(1<<i)+1;i2++)
        {
            int kk=rmq[i2][i-1];
            int kkk=rmq[i2+(1<<(i-1))][i-1];
            rmq[i2][i]=(h[kk]<h[kkk] ? kk : kkk);
        }
    }
    for (int i=0;i<canh.size();i++)
    {
        if (h[canh[i].first]<h[canh[i].second]) swap(canh[i].first,canh[i].second);
        cal[canh[i].first]=i+1;
    }
    vector<int> dinh;
    for (int i=1;i<=m;i++)
    {
        dinh.clear();
        int k;
        cin >> k;
        for (int i=1;i<=k;i++)
        {
            int kk;
            cin >> kk;
            dinh.push_back(kk);
        }
        sort (dinh.begin(),dinh.end(),cmp);
        int m=dinh.size()-1;
        for (int i=0;i<m;i++)
        {
            dinh.push_back(getlca(dinh[i],dinh[i+1]));
        }
        sort (dinh.begin(),dinh.end(),cmp);
        dinh.resize(unique(dinh.begin(),dinh.end())-dinh.begin());
        m=dinh.size()-1;
        for (int i=0;i<m;i++)
        {
            int u=getlca(dinh[i],dinh[i+1]);
            int v=dinh[i+1];
            ke2[u].push_back(v);
            ke2[v].push_back(u);
        }
        // for (int i=0;i<dinh.size();i++)
        // {
        //     cout << dinh[i] << " ";
        // }
        // cout << '\n';
        int kkk=0,minn=n+1;
        for (int i=0;i<=m;i++)
        {
            if (minn>h[dinh[i]])
            {
                kkk=dinh[i];
                minn=h[dinh[i]];
            }
        }
        dfs2(kkk,0);
        // gt[kkk]++;
        // gt2[kkk]--;
        //end
        for (int i=0;i<=m;i++) ke2[dinh[i]].clear();
    }
    dfs3(1,0);
    //for (int i=1;i<=n;i++) cout << gt[i] << " ";
    // cout << '\n';
    cout << kq.size() << '\n';
    sort (kq.begin(),kq.end(),cmp2);
    for (int i=0;i<kq.size();i++) cout << cal[kq[i]] << " ";
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0;i<ke[u].size();i++)
      |                  ~^~~~~~~~~~~~~
railway.cpp: In function 'void dfs3(int, int)':
railway.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=0;i<ke[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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i=0;i<ke2[u].size();i++)
      |                  ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:110: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]
  110 |     for (int i=0;i<canh.size();i++)
      |                  ~^~~~~~~~~~~~
railway.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for (int i=0;i<kq.size();i++) cout << cal[kq[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