Submission #1096054

#TimeUsernameProblemLanguageResultExecution timeMemory
1096054proplayerRailway (BOI17_railway)C++14
0 / 100
86 ms98316 KiB
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const lli maxN = 1e5 + 5;
const lli LG = 17;
lli sp[LG][2 * maxN],id1[2 * maxN],lg[2 * maxN];
lli t,t1,dep[maxN],id[maxN];
lli n,k,m,u[maxN],v[maxN],s,p[maxN],val[maxN],in[maxN];
vector<lli> adj[maxN],adjvt[maxN],vtnode,st;
struct Tedge
{
    lli u,v,w;
}
evt[maxN],e[maxN];
void dfs(lli u,lli par)
{
    lli node = ++t1;
    id1[node] = u;sp[0][++t] = node;
    id[u] = node;in[u] = t;
    for (lli 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 (lli i = 2;i <= t;++i) lg[i] = lg[i / 2] + 1;
    for (lli j = 1;j < LG;++j)
        for (lli i = 1;i <= t - (1 << j) + 1;++i)
        sp[j][i] = min(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);

}
lli lca(lli u,lli v)
{
    lli l = in[u],r = in[v];
    if (l > r) swap(l,r);
    lli k = lg[r - l + 1];
    return id1[min(sp[k][l],sp[k][r - (1 << k) + 1])];
}
lli cost(lli u,lli v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}
void input()
{
    cin >> n >> m >> k;
    for (lli i = 1;i < n;++i)
    {
        lli 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(lli x,lli y)
{
    return id[x] < id[y];
}
void buildtree()
{
    vtnode.clear();
    sort(u + 1,u + s + 1,cmp);
    vtnode.push_back(u[s]);
    for (lli 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 (lli v : vtnode) adjvt[v].clear();
    st.clear();st.push_back(vtnode[0]);
    val[vtnode[0]]--;
    for (lli 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 (lli i = 0;i < vtnode.size();++i)
    {
        val[vtnode[i]] = val[vtnode[i]] - adjvt[vtnode[i]].size() + 1;
    }
}
void calc(lli u)
{
    for (lli v : adj[u])
    {
        if (v == p[u]) continue;
        calc(v);
        val[u] += val[v];
    }
}
void solve()
{
    while (m--)
    {
        cin >> s;
        for (lli i = 1;i <= s;++i) cin >> u[i];
        buildtree();
    }
    calc(1);
    lli cnt = 0;
    for (lli i = 1;i <= n;++i)
    {
        lli 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 (lli i = 1;i <= n;++i)
    {
        lli 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);
    lli t;
    input();
    solve();
}

Compilation message (stderr)

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