Submission #1096935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096935		kingdragon	Railway (BOI17_railway)	C++14	100 / 100	81 ms	29388 KiB

railway

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iil pair<ll,ll>
#define iiil pair<ll,pair<ll,ll>>
#define oo 1e18
#define check(n) (prime[n>>6]&(1<<((n&63)>>1)))
#define set(n) prime[n>>6]|=(1<<((n&63)>>1))
using namespace std;
const int N=3e5+5;
const ll Mod=1e9+7;
const ll MOD=13141702292180207;
const int dx[]={-1,0,0,1};
const int dy[]={0,-1,1,0};
 
 
int n,m,k,g[N],par[N][19],LOG=17, depth[N];
int in[N], out[N], ti=0, pi[N], dem[N];
vector<ii> a[N];
vector<int> res;
bool cha(int u,int v)
{
    if (in[u]<in[v] && out[v]<out[u]) return true;
    return false;
}
bool cmp(int u,int v)
{
    return in[u]<in[v];
}
void dfs(int u)
{
    in[u]=++ti;
    for (ii i: a[u])
    {
        int v=i.F;
        if (v==par[u][0]) continue;
        par[v][0]=u;
        g[v]=i.S;
        depth[v]=depth[u]+1;
        dfs(v);
    }
    out[u]=++ti;
}
 
int lca(int u,int v)
{
    if (depth[u]<depth[v]) swap(u,v);
    for (int i=LOG;i>=0;i--)
        if (depth[par[u][i]]>=depth[v]) u=par[u][i];
    
    if (u==v) return v;
    for (int i=LOG;i>=0;i--)
    {
        if (par[u][i]!=par[v][i]) 
        {
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[v][0];
}

stack<int> st;
void slo()
{
    sort(pi+1,pi+1+ti, cmp);
    int x=ti;
    for (int i=2;i<=ti;i++) pi[++x]=lca(pi[i],pi[i-1]);
    ti=x; x=1;
    sort(pi+1,pi+1+ti, cmp);
    pi[x]=pi[1];
    for (int i=2;i<=ti;i++) 
    if (pi[i]!=pi[i-1]) pi[++x]=pi[i];
    for (int i=1;i<=x;i++)
    {
        // cout << pi[i] << ' ';
        int u=pi[i];
        while (!st.empty() && !cha(st.top(),u)) st.pop();
        if (!st.empty()) dem[u]++, dem[st.top()]--;
        st.push(u);
    }
    while (!st.empty()) st.pop();
    // cout << '\n';
}

void dfs2(int u)
{
    for (ii i: a[u])
    {
        if (par[u][0]==i.F) continue;
        dfs2(i.F);
        dem[u]+=dem[i.F];
    }
    if (dem[u]>=k) res.pb(g[u]);
}
void slove()
{
    cin >> n >> m >> k;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        a[u].pb(ii(v,i));
        a[v].pb(ii(u,i));
    }
    g[1]=0; depth[1]=1;
    par[1][0]=0;
    dfs(1);
    for (int j=1;j<=LOG;j++)
        for (int i=1;i<=n;i++) par[i][j]=par[par[i][j-1]][j-1];
    
    for (int j=1;j<=m;j++)
    {
        int x, u, v;
        cin >> x; ti=x;
        for (int i=1;i<=x;i++) cin >> pi[i];
        slo();
    }
 
    dfs2(1);
    cout << res.size() << '\n';
    sort(res.begin(),res.end());
    for (int i: res) cout << i << ' ';
}
int main()
{
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    int T=1;
    //cin >> T;
    while(T--) slove();
}

Compilation message (stderr)

railway.cpp: In function 'void slove()':
railway.cpp:118:16: warning: unused variable 'u' [-Wunused-variable]
  118 |         int x, u, v;
      |                ^
railway.cpp:118:19: warning: unused variable 'v' [-Wunused-variable]
  118 |         int x, u, v;
      |                   ^

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