oj.uz

Submission #838401

# Submission time Handle Problem Language Result Execution time Memory
838401 2023-08-26T19:23:09 Z finn__ Werewolf (IOI18_werewolf) C++17
0 / 100
 302 ms 44432 KB 
#include <bits/stdc++.h>

#include "werewolf.h"

using namespace std;

struct dsu
{
    vector<int> p;
    vector<vector<int>> g;

    dsu(size_t n) { p = vector<int>(n, -1); }

    int repr(int u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }

    void add_node(int u, vector<int> const &adj)
    {
        for (auto const &v : adj)
            if (repr(v) != u)
                p[repr(v)] = u;
    }

    int dfs(vector<vector<int>> const &g, vector<pair<int, int>> &subtree_range, int u, int i = 0)
    {
        subtree_range[u].first = i++;
        for (int const &v : g[u])
            i = dfs(g, subtree_range, v, i);
        subtree_range[u].second = i - 1;
        return i;
    }

    vector<pair<int, int>> euler_tour()
    {
        vector<vector<int>> g(p.size());
        int root = -1;
        for (int i = 0; i < p.size(); ++i)
            if (p[i] != -1)
                g[p[i]].push_back(i);
            else
                root = i;
        assert(root != -1);
        vector<pair<int, int>> subtree_range(p.size());
        dfs(g, subtree_range, root);
        return subtree_range;
    }
};

struct fenwick_tree
{
    vector<int> t;

    fenwick_tree(size_t n) { t.resize(n); }

    void update(int i, int x)
    {
        ++i;
        while (i <= t.size())
            t[i - 1] += x, i += i & -i;
    }

    int range_sum(int i, int j)
    {
        int x = 0;
        ++j;
        while (j)
            x += t[j - 1], j -= j & -j;
        while (i)
            x -= t[i - 1], i -= i & -i;
        return x;
    }
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R)
{
    int const Q = S.size();

    vector<vector<int>> g(N);
    for (size_t i = 0; i < X.size(); ++i)
        g[min(X[i], Y[i])].push_back(max(X[i], Y[i]));

    vector<int> root1(Q), p(Q);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&L](int const &i, int const &j)
         { return L[i] > L[j]; });

    dsu d(N);
    for (int i = N - 1, j = 0; i >= 0; --i)
    {
        d.add_node(i, g[i]);
        while (j < p.size() && L[p[j]] == i)
            root1[p[j]] = d.repr(S[p[j]]), ++j;
    }

    vector<pair<int, int>> subtree_range1 = d.euler_tour();

    for (int i = 0; i < N; ++i)
        g[i].clear();
    for (size_t i = 0; i < X.size(); ++i)
        g[max(X[i], Y[i])].push_back(min(X[i], Y[i]));

    vector<int> root2(Q);
    sort(p.begin(), p.end(), [&R](int const &i, int const &j)
         { return R[i] < R[j]; });

    d = dsu(N);
    for (int i = 0, j = 0; i < N; ++i)
    {
        d.add_node(i, g[i]);
        while (j < p.size() && R[p[j]] == i)
            root2[p[j]] = d.repr(E[p[j]]), ++j;
    }

    vector<pair<int, int>> subtree_range2 = d.euler_tour();

    fenwick_tree tree(N);
    vector<int> tour1(N);
    for (int i = 0; i < N; ++i)
        tour1[subtree_range1[i].first] = i;
    vector<pair<int, int>> begin_queries, end_queries;
    for (int i = 0; i < Q; ++i)
    {
        begin_queries.emplace_back(subtree_range1[root1[i]].first, i);
        end_queries.emplace_back(subtree_range1[root1[i]].second, i);
    }
    sort(begin_queries.begin(), begin_queries.end());
    sort(end_queries.begin(), end_queries.end());
    vector<int> ans(Q);

    auto it = begin_queries.begin(), jt = end_queries.begin();

    for (int i = 0; i < N; ++i)
    {
        while (it != begin_queries.end() && it->first == i)
            ans[it->second] = -tree.range_sum(subtree_range2[root2[it->second]].first, subtree_range2[root2[it->second]].second), ++it;
        tree.update(subtree_range2[tour1[i]].first, 1);
        while (jt != end_queries.end() && jt->first == i)
            ans[jt->second] += tree.range_sum(subtree_range2[root2[jt->second]].first, subtree_range2[root2[jt->second]].second), ++jt;
    }

    for (int &x : ans)
        x = min(1, x);
    return ans;
}

Compilation message

werewolf.cpp: In member function 'std::vector<std::pair<int, int> > dsu::euler_tour()':
werewolf.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < p.size(); ++i)
      |                         ~~^~~~~~~~~~
werewolf.cpp: In member function 'void fenwick_tree::update(int, int)':
werewolf.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while (j < p.size() && L[p[j]] == i)
      |                ~~^~~~~~~~~~
werewolf.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         while (j < p.size() && R[p[j]] == i)
      |                ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 44432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -