Submission #1096041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096041		vjudge1	Railway (BOI17_railway)	C++17	0 / 100	54 ms	67664 KiB

railway

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 1e5 + 5;
const int LG = 17;
int sp[LG][2 * maxN],id1[2 * maxN],lg[2 * maxN];
int t,t1,dep[maxN],id[maxN];
int n,k,m,u[maxN],v[maxN],s,p[maxN],val[maxN],in[maxN];
vector<int> adj[maxN],adjvt[maxN],vtnode,st;
struct Tedge
{
    int u,v,w;
}
evt[maxN],e[maxN];
void dfs(int u,int par)
{
    int node = ++t1;
    id1[node] = u;sp[0][++t] = node;
    id[u] = node;in[u] = t;
    for (int v : adj[u])
    {
        if (v == par) continue;
        sp[0][++t] = node;
        dep[v] = dep[u] + 1;
        dfs(v,u);
    }
    p[u] = par;
}
void pre()
{
    lg[1] = 0;
    for (int i = 2;i <= t;++i) lg[i] = lg[i / 2] + 1;
    for (int j = 1;j < LG;++j)
        for (int i = 1;i <= t - (1 << j) + 1;++i)
        sp[j][i] = min(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);

}
int lca(int u,int v)
{
    int l = in[u],r = in[v];
    if (l > r) swap(l,r);
    int k = lg[r - l + 1];
    return id1[min(sp[k][l],sp[k][r - (1 << k) + 1])];
}
int cost(int u,int v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}
void input()
{
    cin >> n >> m >> k;
    for (int i = 1;i < n;++i)
    {
        int u,v;
        cin >> u >> v;
        e[i].u = u;e[i].v = v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    t = t1 = 0;dep[1] = 0;
    dfs(1,0);
    pre();
}
bool cmp(int x,int y)
{
    return id[x] < id[y];
}
void buildtree()
{
    vtnode.clear();
    sort(u + 1,u + s + 1,cmp);
    vtnode.push_back(u[s]);
    for (int i = 1;i < s;++i)
    {
        vtnode.push_back(u[i]);
        vtnode.push_back(lca(u[i],u[i + 1]));
    }
    sort(vtnode.begin(),vtnode.end());
    auto ip = unique(vtnode.begin(),vtnode.end());
    vtnode.resize(ip - vtnode.begin());
    sort(vtnode.begin(),vtnode.end(),cmp);
    for (int v : vtnode) adjvt[v].clear();
    st.clear();st.push_back(vtnode[0]);
    for (int i = 1;i < vtnode.size();++i)
    {
        if (!st.empty() && lca(st.back(),vtnode[i]) != st.back()) st.pop_back();
        adjvt[st.back()].push_back(vtnode[i]);
        st.push_back(vtnode[i]);
    }
    for (int i = 0;i < vtnode.size();++i)
    {
        if (adjvt[vtnode[i]].size() == 0) val[vtnode[i]]++;
        else val[vtnode[i]] = val[vtnode[i]] - adjvt[vtnode[i]].size();
    }
}
void calc(int u)
{
    for (int v : adj[u])
    {
        if (v == p[u]) continue;
        calc(v);
        val[u] += val[v];
    }
}
void solve()
{
    while (m--)
    {
        cin >> s;
        for (int i = 1;i <= s;++i) cin >> u[i];
        buildtree();
    }
    calc(1);
    int cnt = 0;
    for (int i = 1;i <= n;++i)
    {
        int tmp;
        if (p[e[i].v] == e[i].u) tmp = val[e[i].v];
        else tmp = val[e[i].u];
        if (tmp >= 2) ++cnt;
    }
    cout << cnt << "\n";
    for (int i = 1;i <= n;++i)
    {
        int tmp;
        if (p[e[i].v] == e[i].u) tmp = val[e[i].v];
        else tmp = val[e[i].u];
        if (tmp >= 2) cout << i << " ";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("D.inp","r",stdin);
//    freopen(D.out","w",stdout);
    int t;
    input();
    solve();
}

Compilation message (stderr)

railway.cpp: In function 'void buildtree()':
railway.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 1;i < vtnode.size();++i)
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0;i < vtnode.size();++i)
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:138:9: warning: unused variable 't' [-Wunused-variable]
  138 |     int t;
      |         ^

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