제출 #1369725

#제출 시각아이디문제언어결과실행 시간메모리
1369725minhpnkRailway (BOI17_railway)C++20
36 / 100
64 ms40104 KiB
#include <bits/stdc++.h>
#define int long long
#define taskname "main"
#define debug(a, l, r) for (int _i = (l); _i <= (r); _i++) cout<<(a)[_i]<<' '; cout<<'\n';
using namespace std;
const int 
    maxN = 1e5,
    maxLg = 20;
int n, m, k, disc,
    h[maxN + 5],
    idx_e[maxN + 5], // idx_e cua node u
    cnt_use[maxN + 5],
    up[maxN + 5][maxLg + 5];
vector <int> 
    w[maxN + 5],
    suit_city;
struct Edge
{
    int u, v;
    void read()
    {
        cin >> u >> v;
    }
    void print()
    {
        cout << u << ' ' << v << '\n';
    }
}; vector <Edge> list_e;
struct Range
{
    int l, r;
} lim[maxN + 5];
struct FenTree
{
    int bit[maxN + 1];
private:
    int get(int u)
    {
        int res = 0;
        for (int i = u; i > 0; i -= i & -i)
            res += bit[i];
        return res;
    }
public:
    void upd(int u, int x)
    {
        for (int i = u; i <= maxN; i += i & -i)
            bit[i] += x;
    }
    int get_r(int l, int r)
    {
        return get(r) - get(l - 1);
    }
} ft;
void init()
{
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        w[u].push_back(v);
        w[v].push_back(u);
        list_e.push_back({u, v});
    }
}
void dfs(int u, int pre)
{
    lim[u].l = ++disc;
    for (int v: w[u])
    {
        if (v != pre)
        {
            h[v] = h[u] + 1;
            up[v][0] = u;
            for (int deg = 1; deg <= maxLg; deg++)
                up[v][deg] = up[up[v][deg - 1]][deg - 1];
            dfs(v, u);
        }
    }
    lim[u].r = disc;
}
int lift(int u, int x)
{
    for (int i = maxLg; i >= 0; i--)
        if (x >> i & 1)
            u = up[u][i];
    return u;
}
int lca(int u, int v)
{
    if (h[u] > h[v])
        swap(u, v);
    v = lift(v, h[v] - h[u]);
    if (u == v)
        return u;
    for (int i = maxLg; i >= 0; i--)
    {
        if (up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
void make_virt(int sz)
{
    stack <int> st;
    for (int i = 1; i < sz; i++)
        suit_city.push_back(lca(suit_city[i], suit_city[i - 1]));
    sort(suit_city.begin(), suit_city.end(), [](int x, int y){
        return lim[x].l < lim[y].l;
    });
    suit_city.erase(unique(suit_city.begin(), suit_city.end()), suit_city.end());
    for (int u: suit_city)
    {
        if (st.empty())
        {
            st.push(u);
            continue;
        }
        while (lift(u, h[u] - h[st.top()]) != st.top())
            st.pop();
        list_e.push_back({st.top(), u});
        st.push(u);
    }
}
void set_idxe()
{
    dfs(1, 0);
    for (int i = 0; i < list_e.size(); i++)
    {
        Edge e = list_e[i];
        if (lim[e.u].l > lim[e.v].l)
            swap(e.u, e.v);
        idx_e[e.v] = i + 1;
    }
    list_e.clear();
}
void add_eval()
{
    for (int i = 1; i <= m; i++)
    {
        int sz; cin >> sz;
        for (int i = 1; i <= sz; i++)
        {
            int u; cin >> u;
            suit_city.push_back(u);
        }
        make_virt(sz);
        suit_city.clear();
    }
}
void upd_path(int u, int v)
{
    if (h[u] > h[v])
        swap(u, v);
    ft.upd(lim[v].l, 1);
    ft.upd(lim[u].l, -1);
}
void solve()
{
    for (Edge e: list_e)
        upd_path(e.u, e.v);
    suit_city.clear();
    for (int i = 1; i <= n; i++)
    {
        if (ft.get_r(lim[i].l, lim[i].r) >= k)
            suit_city.push_back(i);
    }
    cout << suit_city.size() << '\n';
    for (int u: suit_city)
        cout << idx_e[u] << ' ';
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    if (fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    init(); set_idxe(); add_eval(); solve();
}

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

railway.cpp: In function 'int main()':
railway.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…