Submission #1086126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086126		_callmelucian	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	127 ms	27540 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

pii refineTree (vector<vector<pii>> &graph, vector<int> &weight, vector<int> &node, int n, int root) {
    vector<int> vis(n + 1), deg(n + 1);
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (graph[i].size() == 1 && i != root) q.push(i);
    for (int u : node) deg[u] = 1;

    int ans = 0;
    while (q.size()) {
        int a = q.front(); q.pop();
        if (vis[a] == graph[a].size()) continue;
        vis[a]++;

        for (auto [b, id] : graph[a]) {
            if (vis[b] == graph[b].size()) continue;
            if (deg[a]) deg[b] ^= 1, ans += weight[id];
            else weight[id] = 0;

            if (++vis[b] + 1 == graph[b].size()) q.push(b);
        }
    }
    return {ans, (deg[root] == 0)};
}

const int mn = 1e5 + 5;
int up[mn][17], num[mn], sz[mn], dist[mn], depth[mn], timeDfs;
vector<vector<pii>> adj;
vector<int> weight;

void dfs (int u, int p, int d, int fromP) {
    dist[u] = dist[p] + fromP, num[u] = ++timeDfs, sz[u] = 1;
    up[u][0] = p, depth[u] = d;
    for (int i = 1; i < 17; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (auto [v, id] : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1, weight[id]);
        sz[u] += sz[v];
    }
}

int goUp (int a, int k) {
    for (int i = 0; i < 17; i++)
        if (k & (1 << i)) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = 16; i >= 0; i--)
        if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

int distance (int a, int b) {
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int depthDist (int a, int b) {
    return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}

bool check (int p, int u) {
    return num[p] <= num[u] && num[u] < num[p] + sz[p];
}

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

    // setup graph
    int n, q; cin >> n >> q;
    adj.resize(n + 1), weight.resize(n);
    fill(all(weight), 1);

    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }

    // find root
    int root = 0;
    vector<int> leaves;
    for (int i = 1; i <= n; i++)
        if (adj[i].size() == 1) root = i, leaves.push_back(i);

    // find initial answer
    int ans; bool correct; tie(ans, correct) = refineTree(adj, weight, leaves, n, root);
    dfs(1, 1, 0, 0);

    vector<bool> vis(n + 1);
    while (q--) {
        int d; cin >> d;

        map<int,int> mp;
        for (int i = 0; i < d; i++) {
            int node; cin >> node;
            mp[node]++;
        }
        if (!correct) mp[root]++;

        // create node list for virtual tree
        vector<int> qry, nodeList;
        for (auto [node, freq] : mp) {
            if (!correct && node == root && freq == 1) qry.push_back(node);
            else if (adj[node].size() == 1 && freq % 2 == 0) qry.push_back(node);
            else if (adj[node].size() > 1 && freq % 2) qry.push_back(node);
        }
        int sz = qry.size();
        for (int u : qry) vis[u] = 1;

        sort(all(qry), [&] (int a, int b) { return num[a] < num[b]; });
        for (int i = 1; i < sz; i++) {
            int tmp = lca(qry[i - 1], qry[i]);
            qry.push_back(tmp);
        }
        sort(all(qry), [&] (int a, int b) { return num[a] < num[b]; });
        filter(qry);

        for (int i = 0; i < qry.size(); i++) {
            if (vis[qry[i]]) nodeList.push_back(i + 1);
            vis[qry[i]] = 0;
        }

        // build virtual tree
        vector<vector<pii>> virtTree(qry.size() + 1);
        stack<int> st;
        vector<int> virtWeight;
        for (int i = 0; i < qry.size(); i++) {
            while (st.size() && !check(qry[st.top()], qry[i])) st.pop();
            if (st.size()) {
                int a = st.top() + 1, b = i + 1, c = depthDist(qry[st.top()], qry[i]) - 2 * distance(qry[st.top()], qry[i]), id = virtWeight.size();
                virtTree[a].emplace_back(b, id);
                virtTree[b].emplace_back(a, id);
                virtWeight.push_back(c);
            }
            st.push(i);
        }

        // find virtual tree's root
        int nroot = 0;
        for (int i = 1; i <= qry.size(); i++)
            if (virtTree[i].size() <= 1) nroot = i;

        int delta; bool curCorrect; tie(delta, curCorrect) = refineTree(virtTree, virtWeight, nodeList, qry.size(), nroot);
        int sumEdge = n + d - 1, oneEdge = ans + d + delta;

        //cout << "pre ans " << delta << " " << sumEdge << " " << oneEdge << "\n";
        if (curCorrect || qry.empty()) cout << 2 * sumEdge - oneEdge << "\n";
        else cout << -1 << "\n";
    }

    return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'pii refineTree(std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<int>&, int, int)':
cleaning.cpp:23:20: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (vis[a] == graph[a].size()) continue;
cleaning.cpp:26:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |         for (auto [b, id] : graph[a]) {
      |                   ^
cleaning.cpp:27:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             if (vis[b] == graph[b].size()) continue;
cleaning.cpp:31:30: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if (++vis[b] + 1 == graph[b].size()) q.push(b);
      |                 ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int, int, int)':
cleaning.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for (auto [v, id] : adj[u]) {
      |               ^
cleaning.cpp: In function 'int main()':
cleaning.cpp:121:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for (auto [node, freq] : mp) {
      |                   ^
cleaning.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int i = 0; i < qry.size(); i++) {
      |                         ~~^~~~~~~~~~~~
cleaning.cpp:146:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i = 0; i < qry.size(); i++) {
      |                         ~~^~~~~~~~~~~~
cleaning.cpp:159:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for (int i = 1; i <= qry.size(); i++)
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30