Submission #1096279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096279		trinhvtuan	Railway (BOI17_railway)	C++17	0 / 100	1012 ms	28872 KiB

railway

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define li pair<ll,int>
#define i2 pair<int,int>
using namespace std;
int n,m,k,sp[100003][19],h[100003],cnt[100003],d[100003],sl=0;
vector<int> b[100003];
vector<i2> a[100003];
vector<int> res;
void dfs(int u,int p){
    for (i2 v:a[u]){
        if (v.se==p) continue;
        sp[v.se][0]=u;
        h[v.se]=h[u]+1;
        dfs(v.se,u);
    }
}
int get(int u,int v){
    if (h[u]<h[v]) swap(u,v);
    int x=h[u]-h[v];
    for (int i=17;i>=0;i--)
        if (x>>i&1) u=sp[u][i];
    if (u==v) return u;
    for (int i=17;i>=0;i--)
    if (sp[u][i]!=sp[v][i]){
        u=sp[u][i];
        v=sp[v][i];
    }
    return sp[0][u];
}
void dfstr(int u,int p,int tt){
    for (i2 v:a[u]){
        if (v.se==p) continue;
        dfstr(v.se,u,v.fi);
        d[u]+=d[v.se];
    }
    if (tt!=-1&&d[u]>0) {
        cnt[tt]++;
    }
}
void dfstr1(int u,int p,int tt){
    for (i2 v:a[u]){
        if (v.se==p) continue;
        dfstr1(v.se,u,v.fi);
        d[u]+=d[v.se];
    }
    if (tt!=-1) {
        cnt[tt]=d[u];
    }
}
void sub1(){
    bool check=1;
    for (int i=1;i<=m;i++){
        cin>>sl;
        if (sl>2) check=0;
        b[i].resize(sl+1);
        for (int j=1;j<=sl;j++) {
            cin>>b[i][j];
        }
    }
    if (check){
        for (int i=1;i<=m;i++){
            if (b[i].size()-1==1) continue;
            int c=get(b[i][1],b[i][2]);
            d[c]-=2;
            d[b[i][1]]++;
            d[b[i][2]]++;
        }
        dfstr1(1,0,-1);
    }
    else {
        for (int i=1;i<=m;i++){
            sl=b[i].size()-1;
            if (sl==1) continue;
            for (int j=1;j<=n;j++) d[j]=0;
            for (int j=2;j<=sl;j++) {
                int c=get(b[i][1],b[i][j]);
                d[c]+=-2;
                d[b[i][1]]++;
                d[b[i][j]]++;
            }
            dfstr(1,0,-1);
        }
    }
    for (int i=1;i<n;i++)
        if (cnt[i]>=k) res.push_back(i);
    cout<<res.size()<<"\n";
    for (int x:res) cout<<x<<" ";
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("SUADUONG.inp","r",stdin);
    //freopen("SUADUONG.out","w",stdout);
    cin>>n>>m>>k;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back({i,v});
        a[v].push_back({i,u});
    }
    dfs(1,0);
    for (int j=1;j<log2(n);j++){
        for (int i=1;i<=n;i++){
            sp[i][j]=sp[sp[i][j-1]][j-1];
        }
    }
    sub1();
    return 0;
}

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