제출 #1365239

#제출 시각아이디문제언어결과실행 시간메모리
1365239hyyhRailway (BOI17_railway)C++20
7 / 100
499 ms27508 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <unordered_map>

#define int long long

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)
#define m_p make_pair

int const N = 1e5+10;

int cnt[N];

class bitsegment{
    struct Node{
        bitset<65> val;
    };
    Node segment[N*4];

public:
    int si;

    void process(){
        process(1,1,si);
    }
    
    void push(int node,int l,int r){
        if(l == r) return;
        else{
            segment[node*2].val |= segment[node].val;
            segment[node*2+1].val |= segment[node].val;
        }
        segment[node].val = 0;
    }
    
    void process(int node,int l,int r){
        push(node,l,r);
        if(l == r) cnt[l] += segment[node].val.count();
        else{
            int md = l+(r-l)/2;
            process(node*2,l,md);
            process(node*2+1,md+1,r);
        }
        segment[node].val.reset();
    }
    
    void set(int node,int l,int r,int lay,int ql,int qr){
        push(node,l,r);
        if(l >= ql && r <= qr){
            segment[node].val.set(lay);
            push(node,l,r);
        }
        else if(l > qr || r < ql) return;
        else{
            int md = l+(r-l)/2;
            set(node*2,l,md,lay,ql,qr);
            set(node*2+1,md+1,r,lay,ql,qr);
        }
    }

    void set(int l,int r,int lay){
        if(l > r) return;
        set(1,1,si,lay,l,r);
    }

    void print(int node,int l,int r){
        push(node,l,r);
        if(l == r){
            cout << segment[node].val << endl;
        }
        else{
            int md = l+(r-l)/2;
            print(node*2,l,md);
            print(node*2+1,md+1,r);
        }
    }

    void print(){
        print(1,1,si);
        cout << "----------------------------------------------------------------" << endl;
    }
};

bitsegment segment;

int nodecnt[N];
int depth[N];
int pos[N];
int rpos[N];
int chain[N];
int chainhead[N];
int par[N];
int edge[N];
int order[N];

int curpos = 0;
int chainid = 0;

vector<pii> adj[N];

void dfs1(int n,int p){
    nodecnt[n] = 1;
    for(auto [k,i]:adj[n]){
        if(k == p) continue;
        par[k] = n;
        edge[k] = i;
        depth[k] = depth[n]+1;
        dfs1(k,n);
        nodecnt[n] += nodecnt[k];
    }
}

void dfs2(int n,int p){
    pos[n] = ++curpos;
    rpos[pos[n]] = n;
    chain[n] = chainid;
    pii hv = {0,-1};
    for(auto [k,i]:adj[n]){
        if(k == p) continue;
        hv = max(hv,{nodecnt[k],k});
    }
    if(hv.s != -1) dfs2(hv.s,n);
    for(auto [k,i]:adj[n]){
        if(k == p || k == hv.s) continue;
        chainhead[++chainid] = k;
        dfs2(k,n);
    }
}

void update(int a,int b,int lay){
    while(chain[a] != chain[b]){
        if(depth[a] < depth[b]) swap(a,b);
        int head = chainhead[chain[a]];
        segment.set(pos[head],pos[a],lay);
        a = par[head];
    }
    if(depth[a] < depth[b]) swap(a,b);
    segment.set(pos[b]+1,pos[a],lay);
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    int m;cin >> m;
    int k;cin >> k;
    segment.si = n;
    for(int i{};i < n-1;i++){
        int a,b;cin >> a >> b;
        adj[a].emplace_back(b,i+1);
        adj[b].emplace_back(a,i+1);
    }
    dfs1(1,1);
    chainhead[0] = 1;
    dfs2(1,1);
    for(int i{};i < m;i++){
        int g;cin >> g;
        int last = 0;
        if(i%64 == 0){
            segment.process();
        }
        for(int j{};j < g;j++){
            int c;cin >> c;
            if(j > 0) update(last,c,i%64);
            last = c;
        }
        //segment.print();
    }
    segment.process();
    vector<int> ans;
    int cnt2 = 0;
    for(int i{2};i <= n;i++){
        if(cnt[i] >= k){
            cnt2++;
            ans.emplace_back(edge[rpos[i]]);
        }
    }
    cout << cnt2 << endl;
    sort(all(ans));
    for(auto a:ans){
        cout << a << " ";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…