Submission #1096064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096064		proplayer	Railway (BOI17_railway)	C++14	100 / 100	109 ms	95848 KiB

railway

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const lli maxN = 1e6 + 5;
const lli LG = 20;
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)
    {
        while (!st.empty() && lca(st.back(),vtnode[i]) != st.back()) st.pop_back();
        //cout << st.size() << " " << st.back() << " " << vtnode[i] << " " << lca(st.back(),vtnode[i]) << "\n";
        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;
    //for (lli i = 0;i < vtnode.size();++i) cout << adjvt[vtnode[i]].size() << " " << vtnode[i] << "\n";
}
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);
    //for (int i = 1;i <= n;++i) cout << val[i] << "\n";
    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 >= k) ++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 >= k) 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:92: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]
   92 |     for (lli i = 0;i < vtnode.size();++i)
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:139:9: warning: unused variable 't' [-Wunused-variable]
  139 |     lli t;
      |         ^

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