Submission #135054

#	Time	Username	Problem	Language	Result	Execution time	Memory
135054		miguel	Railway (BOI17_railway)	C++14	100 / 100	171 ms	24180 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
#define nmax 301
const ll mod = 998244353;
int n, m, k, timer, up[100001][18], tin[100001], tout[100001], cnt[100001];
vi g[100001];
pi ed[100001];

void dfs(int nod, int p){
    tin[nod]=timer++;
    up[nod][0]=p;
    for(int i=1; i<=17; i++) up[nod][i]=up[up[nod][i-1]][i-1];
    for(int i : g[nod]){
        if(i!=p) dfs(i, nod);
    }
    tout[nod]=timer++;
}

bool check(int anc, int x){
    if(tin[anc]<=tin[x] && tout[x]<=tout[anc]) return 1;
    else return 0;
}

int lca(int x, int y){
    if(check(x, y)) return x;
    else if(check(y, x)) return y;
    for(int i=17; i>=0; i--){
        if(check(up[x][i], y)==0) x=up[x][i];
    }
    return up[x][0];
}

void dfs2(int nod, int p){
    for(int i: g[nod]){
        if(i!=p){
            dfs2(i, nod);
            cnt[nod]+=cnt[i];
        }
    }
}

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

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>k;
    for(int i=1; i<n; i++){
        int a, b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
        ed[i]={a, b};
    }
    dfs(1, 1);
    //int q; cin>>q; for(int i=1; i<=q; i++){int x, y; cin>>x>>y; cout<<lca(x, y);}
    for(int i=1; i<=m; i++){
        int s;
        vi v;
        cin>>s;
        for(int j=1; j<=s; j++){
            int x;
            cin>>x;
            v.pb(x);
        }
        sort(v.begin(), v.end(), cmp);
        for(int j=0; j<v.size(); j++){
            int x=v[j], y=v[(j+1)%v.size()];
            cnt[x]++, cnt[y]++, cnt[lca(x, y)]-=2;
        }
    }
    dfs2(1, 1);
    vi ans;
    for(int i=1; i<n; i++){
        int a=ed[i].x, b=ed[i].y;
        if(tin[a]>tin[b]) swap(a, b);
        if(cnt[b]>=2*k) ans.pb(i);
    }
    cout<<ans.size()<<"\n";
    for(int i : ans) cout<<i<<" ";
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v.size(); j++){
                      ~^~~~~~~~~

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