제출 #943507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943507		Zero_OP	Railway (BOI17_railway)	C++14	100 / 100	70 ms	22976 KiB

railway

#include<bits/stdc++.h>

using namespace std;
using int64 = int64_t;

#define     REP(i, n) for(int i = 0, _n = n; i < _n; ++i)
#define    REPD(i, n) for(int i = n - 1; i >= 0; --i)
#define  FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i)
#define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i)
#define          left __left
#define         right __right
#define          prev __prev
#define          next __next
#define           div __div
#define            pb push_back
#define            pf push_front
#define         sz(v) (int)v.size()
#define      range(v) begin(v), end(v)
#define    compact(v) v.erase(unique(range(v)), end(v))
#define      debug(v) "[" #v " = " << (v) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            a = b;
            return true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            a = b;
            return true;
        }
        return false;
    }

template<int dimension, class T>
struct vec : public vector<vec<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {}
};

template<class T>
struct vec<1, T> : public vector<T> {
    vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};

void init(void);
void process(void);

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

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) {
        init();
        process();
    }

    return 0;
}

const int MAX = 1e5 + 5;

int n, m, k, timer_dfs;
int tour[MAX], cnt[MAX], eu[MAX], ev[MAX], depth[MAX], par[MAX], head[MAX], pos[MAX], heavy[MAX], count_children[MAX], diff[MAX], edge_indices[MAX];
vector<int> adj[MAX];

void init(){
    cin >> n >> m >> k;
    REP(i, n - 1){
        int u, v;
        cin >> u >> v;
        adj[u].pb(i);
        adj[v].pb(i);
        eu[i] = u, ev[i] = v;
    }
}

void pre_dfs(int u, int pre){
    count_children[u] = 1;
    for(int id : adj[u]) if(id != pre){
        int v = eu[id] ^ ev[id] ^ u;
        depth[v] = depth[u] + 1;
        par[v] = u;
        edge_indices[v] = id;
        pre_dfs(v, id);
        count_children[u] += count_children[v];
        if(count_children[heavy[u]] < count_children[v]){
            heavy[u] = v;
        }
    }
}

void decompose(int u, int c){
    head[u] = c;
    tour[pos[u] = ++timer_dfs] = u;

    if(heavy[u]){
        decompose(heavy[u], c);
        for(int id : adj[u]){
            int v = eu[id] ^ ev[id] ^ u;
            if(par[v] == u and v != heavy[u]){
                decompose(v, v);
            }
        }
    }
}

int getLCA(int u, int v){
    while(head[u] != head[v]){
        if(depth[head[u]] < depth[head[v]]){
            v = par[head[v]];
        }
        else{
            u = par[head[u]];
        }
    }
    if(depth[u] < depth[v]) return u;
    else return v;
}

void add_range_sum(int l, int r, int v){
    diff[l] += v;
    diff[r + 1] -= v;
}

void add_sum(int u, int v){
    while(head[u] != head[v]){
        if(depth[head[u]] < depth[head[v]]) swap(u, v);
        add_range_sum(pos[head[u]], pos[u], 1);
        u = par[head[u]];
    }

    if(u != v){
        if(depth[u] > depth[v]) swap(u, v);
        add_range_sum(pos[u] + 1, pos[v], 1);
    }
}

bool is_parent(int u, int v){
    return pos[u] <= pos[v] and pos[v] <= pos[u] + count_children[u] - 1;
}

void solve_difference(){
    FOR(i, 2, n){
        diff[i] += diff[i - 1];
        cnt[edge_indices[tour[i]]] = diff[i];
    }
}

void process(){
    pre_dfs(1, -1);
    decompose(1, 1);

    while(m--){
        int s;
        cin >> s;
        vector<int> ar(s);
        REP(i, s) cin >> ar[i];

        sort(range(ar), [&](int a, int b){
            return pos[a] < pos[b];
        });

        REP(i, s - 1){
            ar.pb(getLCA(ar[i], ar[i + 1]));
        }

        sort(range(ar), [&](int a, int b){
            return pos[a] < pos[b];
        });

        compact(ar);

        stack<int> stack_vertices;
        stack_vertices.push(ar[0]);
        FOR(i, 1, sz(ar) - 1){
            while(!stack_vertices.empty() and !is_parent(stack_vertices.top(), ar[i])){
                stack_vertices.pop();
            }

            add_sum(stack_vertices.top(), ar[i]);
            stack_vertices.push(ar[i]);
        }
    }

    solve_difference();

    vector<int> res;
    REP(i, n - 1){
        if(cnt[i] >= k){
            res.pb(i);
        }
    }

    cout << sz(res) << '\n';
    for(int i : res) cout << i + 1 << ' ';
}

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

railway.cpp: In function 'int main()':
railway.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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