Submission #129905

#	Time	Username	Problem	Language	Result	Execution time	Memory
129905		Abelyan	Railway (BOI17_railway)	C++17	100 / 100	204 ms	25712 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=1e5+10;
const ll MOD=1e9+7;
 
int n,m,k,lg,timer,tin[N],tout[N],anc[N][20],qan[N];;
vector<pir> g[N];
vector<int> ans;
 
void dfs(int v,int par=0){
    tin[v]=timer++;
    anc[v][0]=par;
    FORT(i,1,lg) anc[v][i]=anc[anc[v][i-1]][i-1];
 
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par){
            continue;
        }
        dfs(to,v);
    }
    tout[v]=timer++;
}
 
bool upper(int a,int b){
    return tin[a]<=tin[b] && tout[b]<=tout[a];
}
 
int lca(int a,int b){
    if (upper(a,b))return a;
    if (upper(b,a))return b;
    FORD(i,lg+1){
        if (!upper(anc[a][i],b)){
            a=anc[a][i];
        }
    }
    return anc[a][0];
}
 
int dfs2(int v,int par=0){
    int tiv=qan[v];
    //cout<<v<<" "<<tiv<<endl;
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par)continue;
        int cur=dfs2(to,v);
        if (cur>=k){
            ans.ad(tv.sc);
        }
        tiv+=cur;
    }
    return tiv;
}
set<int> st;
int get(int a){
    //cout<<tin[a]<<endl;
    if (st.lower_bound(tin[a])!=st.end() && *st.lower_bound(tin[a])==tin[a]) return a;
    FORD(i,lg+1){
        if (st.lower_bound(tin[anc[a][i]])==st.lower_bound(tout[anc[a][i]]+1)){
            a=anc[a][i];
            //cout<<"hey "<<a<<endl;
        }
    }
    return anc[a][0];
}
 
int main(){
    fastio;
    srng;
    cin>>n>>m>>k;
    FOR(i,n-1){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        g[a].ad({b,i+1});
        g[b].ad({a,i+1});
    }
    while((1<<lg)<=n)lg++;
    dfs(0);
    FOR(ttt,m){
        int s;
        cin>>s;
        vector<pir> vec;
        FOR(i,s){
            int a;
            cin>>a;
            a--;
            vec.ad({tin[a],a});
        }
        sort(all(vec));
        int lc=vec[0].sc;
        FORT(i,1,s-1){
            lc=lca(lc,vec[i].sc);
        }
        //cout<<lc<<endl;
        st.insert(tin[lc]);
        //cout<<"added "<<tin[lc]<<endl;
        FOR(i,s){
            qan[vec[i].sc]++;
            int verevin=get(vec[i].sc);
            //cout<<vec[i].sc<<" "<<verevin<<endl;
            qan[verevin]--;
            st.insert(tin[vec[i].sc]);
            //cout<<"added "<<tin[vec[i].sc]<<endl;
        }
        st.clear();
 
    }
    assert(dfs2(0)==0);
    cout<<ans.size()<<endl;
    sort(all(ans));
    FOR(i,ans.size()){
        cout<<ans[i]<<" ";
    }
    return 0;
}
 

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
railway.cpp:135:5: note: in expansion of macro 'FOR'
     FOR(i,ans.size()){
     ^~~

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