Submission #1282339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282339		escobrand	Railway (BOI17_railway)	C++20	100 / 100	64 ms	26988 KiB

railway

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<int,int> pii;

const int maxn = 1e5 + 10;
int i,n,m,t;
vector<pii> adj[maxn];
int in[maxn],out[maxn],p[maxn][20],req;

void dfs(int i,int pa)
{
  in[i] = ++t;
  p[i][0] = pa;
  for(int j = 1;j<20;j++)p[i][j] = p[p[i][j-1]][j-1];
  for(pii k : adj[i])
  {
      if(k.fi==pa)continue;
    dfs(k.fi,i);
  }
  out[i] = t;
}

bool cmp(int &i,int &j)
{
  return in[i] < in[j];
}

void filter(vector <int>& v)
{
    sort(all(v),cmp);
    v.resize(unique(all(v))-v.begin());
}

int lca(int u,int v)
{
    if(!cmp(u,v))swap(u,v);
    if(u==v)return u;
    for(int j = 19;j>=0;j--)
    {
        if(p[v][j] && cmp(u,p[v][j]))v = p[v][j];
    }
    return p[v][0];
}
int dp[maxn];

void solve()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int &k : v)cin>>k;
    filter(v);
    for(int i = 1;i<n;i++)
    {
        v.pb(lca(v[i],v[i-1]));
    }
    filter(v);
    stack<int>st;
    for(int k : v)
    {
        while(st.size() && out[k]>out[st.top()])st.pop();
        if(st.size())
        {
            dp[k]++;
            dp[st.top()]--;
        }
        st.push(k);
    }
}
vector<int>ans;
void cal(int i,int pa)
{
    for(pii k : adj[i])
    {
        if(k.fi==pa)continue;
        cal(k.fi,i);
        if(dp[k.fi]>=req)ans.pb(k.se);
        dp[i] += dp[k.fi];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    if(fopen("a.inp","r"))
    {
        freopen("a.inp","r",stdin);
        freopen("a.out","w",stdout);
    }


    cin>>n>>m>>req;

    for(i =1;i<n;i++)
    {
      int u,v;
      cin>>u>>v;
      adj[u].pb(mk(v,i));
      adj[v].pb(mk(u,i));
    }
    dfs(1,0);
    while(m--)
    {
        solve();
    }

    cal(1,0);
    sort(all(ans));
    cout<<ans.size()<<'\n';
    for(int k : ans)cout<<k<<' ';


    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("a.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("a.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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