제출 #502219

#제출 시각아이디문제언어결과실행 시간메모리
502219LoboRailway (BOI17_railway)C++17
59 / 100
518 ms23004 KiB
#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

ii n, m, k, cnt[maxn], bit[maxn], p[maxn][25], ps[maxn], h[maxn];
vector<pair<ii,ii>> edg, g[maxn];
ii tin[maxn], tout[maxn], timer = 1;

void att(ii pos, ii val) {
    for(ii i = pos; i <= n; i+= i&-i) {
        bit[i]+= val;
    }
}

ii qr(ii pos) {
    ii val = 0;
    for(ii i = pos; i > 0; i-= i&-i) {
        val+= bit[i];
    }
    return val;
}

ii lca(ii u, ii v) {
    if(h[u] < h[v]) swap(u,v);

    for(ii i = 20; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }

    if(u == v) {
        return u;
    }

    for(ii i = 20; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }

    return p[u][0];
}

void dfst(ii u, ii ant, ii id) {
    //.fr = pai .sc = filho
    if(u != 1 && edg[id].fr == u) swap(edg[id].fr,edg[id].sc);

    tin[u] = timer++;

    for(auto V : g[u]) {
        ii v = V.fr;
        ii id1 = V.sc;
        if(v == ant) continue;
        
        dfst(v,u,id1);
    }

    tout[u] = timer-1;
}

void dfslca(ii u, ii ant, ii id) {
    //.fr = pai .sc = filho
    if(u != 1 && edg[id].fr == u) swap(edg[id].fr,edg[id].sc);

    p[u][0] = ant;
    for(ii i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }

    for(auto V : g[u]) {
        ii v = V.fr;
        ii id1 = V.sc;
        if(v == ant) continue;
        h[v] = h[u]+1;
        
        dfslca(v,u,id1);
    }
}

void dfsps(ii u, ii ant) {
    for(auto V : g[u]) {
        ii v = V.fr;
        if(v == ant) continue;
        
        dfsps(v,u);
        ps[u]+= ps[v];
    }
}

void solve() {
    cin >> n >> m >> k;

    if(n <= 10000 && m <= 2000) {

        for(ii i = 0; i < n-1; i++) {
            ii a, b;
            cin >> a >> b;

            g[a].pb(mp(b,i));
            g[b].pb(mp(a,i));
            edg.pb(mp(a,b));
        }

        dfst(1,0,0);

        for(ii i = 0; i < m; i++) {
            ii s; cin >> s;
            vector<ii> v;
            for(ii j = 0; j < s; j++) {
                ii u; cin >> u;
                v.pb(u);
                att(tin[u],+1);
            }

            for(ii i = 0; i < n-1; i++) {
                ii u = edg[i].fr;
                ii v = edg[i].sc;

                ii sum = qr(tout[v]) - qr(tin[v]-1);

                if(sum != 0 && sum-s != 0) cnt[i]++;
            }

            for(auto u : v) att(tin[u],-1);
        }
    

    }
    else if(k == m) {
        for(ii i = 0; i < n-1; i++) {
            ii a, b;
            cin >> a >> b;

            g[a].pb(mp(b,i));
            g[b].pb(mp(a,i));
            edg.pb(mp(a,b));
        }

        h[1] = 0;
        dfslca(1,1,0);

        while(m--) {
            ii s; cin >> s;
            ii u, v;
            cin >> u >> v;

            ii lc = lca(u,v);

            ps[u]++;
            ps[v]++;
            ps[lc]-= 2;  
        }

        dfsps(1,1);
        for(ii i = 0; i < n-1; i++) {
            ii v = edg[i].sc;
            cnt[i] = ps[v];
        }
    }
    else {

        for(ii i = 0; i < n-1; i++) {
            ii a, b;
            cin >> a >> b;

            g[a].pb(mp(b,i));
            g[b].pb(mp(a,i));
            edg.pb(mp(a,b));
        }

        dfst(1,0,0);

        for(ii i = 0; i < m; i++) {
            ii s; cin >> s;
            vector<ii> v;
            ii mn = n+1;
            ii mx = 0;
            for(ii j = 0; j < s; j++) {
                ii u; cin >> u;
                mn = min(mn,tin[u]);
                mx = max(mx,tin[u]);
            }

            att(mn,+1);
            att(mx,-1);
        }

        for(ii i = 0; i < n-1; i++) {
            ii u = edg[i].fr;
            ii v = edg[i].sc;

            cnt[i] = qr(tin[u]);
        
        }
    }
    

    vector<ii> ans;
    for(ii i = 0; i < n-1; i++) {
        if(cnt[i] >= k) ans.pb(i+1);
    }

    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;

}

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

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void solve()':
railway.cpp:138:20: warning: unused variable 'u' [-Wunused-variable]
  138 |                 ii u = edg[i].fr;
      |                    ^
railway.cpp:212:16: warning: unused variable 'v' [-Wunused-variable]
  212 |             ii v = edg[i].sc;
      |                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...