Submission #293937

#	Time	Username	Problem	Language	Result	Execution time	Memory
293937		Kastanda	Werewolf (IOI18_werewolf)	C++11	100 / 100	824 ms	99172 KiB

werewolf

// M
#include<bits/stdc++.h>
#include "werewolf.h"
#define pb push_back
using namespace std;
const int N = 400005;
int n, m, q, P[N], la[N], ra[N], lb[N], rb[N];
pair < int , int > targ[N];
vector < int > Adj[N], A[N], Event[N];
vector < pair < int , int > > Qvent[N];
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return ;
        if (P[v] > P[u])
                swap(v, u);
        for (int a : A[u])
                A[v].pb(a);
        A[u].clear();
        P[v] += P[u];
        P[u] = v;
}
inline void Init()
{
        memset(P, -1, sizeof(P));
        for (int i = 0; i < n; i ++)
                A[i].clear(), A[i].pb(i), Event[i].clear();
}

vector < int > check_validity(int _n, vector < int > _U, vector < int > _V, vector < int > S, vector < int > E, vector < int > L, vector < int > R)
{
        n = _n;
        m = (int)_U.size();
        q = (int)S.size();
        for (int i = 0; i < m; i ++)
        {
                Adj[_U[i]].push_back(_V[i]);
                Adj[_V[i]].push_back(_U[i]);
        }

        Init();
        for (int i = 0; i < q; i ++)
                Event[R[i]].pb(i);
        for (int i = 0; i < n; i ++)
        {
                for (int u : Adj[i])
                        if (u < i)
                                Merge(u, i);
                for (int e : Event[i])
                        targ[e] = make_pair(Find(E[e]), A[Find(E[e])].size());
        }
        vector < int > vec;
        for (int i = 0; i < n; i ++)
                if (Find(i) == i)
                        vec = A[i];
        assert(vec.size() == n);
        vector < int > rev(n);
        for (int i = 0; i < n; i ++)
                rev[vec[i]] = i;
        for (int i = 0; i < q; i ++)
                la[i] = rev[targ[i].first], ra[i] = la[i] + targ[i].second;

        Init();
        for (int i = 0; i < q; i ++)
                Event[L[i]].pb(i);
        for (int i = n - 1; i >= 0; i --)
        {
                for (int u : Adj[i])
                        if (u > i)
                                Merge(u, i);
                for (int e : Event[i])
                        targ[e] = make_pair(Find(S[e]), A[Find(S[e])].size());
        }

        vector < int > dec;
        for (int i = 0; i < n; i ++)
                if (Find(i) == i)
                        dec = A[i];
        assert(dec.size() == n);
        for (int i = 0; i < n; i ++)
                rev[dec[i]] = i;
        for (int i = 0; i < q; i ++)
                lb[i] = rev[targ[i].first], rb[i] = lb[i] + targ[i].second;

        for (int i = 0; i < n; i ++)
                rev[vec[i]] = i;
        for (int i = 0; i < n; i ++)
                dec[i] = rev[dec[i]];

        for (int i = 0; i < q; i ++)
        {
                if (rb[i])
                        Qvent[rb[i] - 1].pb({i, 1});
                if (lb[i])
                        Qvent[lb[i] - 1].pb({i, -1});
        }

        vector < int > F(N, 0);
        auto AddFen = [&](int i, int val){
                for (i ++; i < N; i += i & - i)
                        F[i] += val;
        };
        auto GetFen = [&](int i){
                int rt = 0;
                for (i ++; i; i -= i & - i)
                        rt += F[i];
                return rt;
        };
        auto GetFenLR = [&](int l, int r){
                return GetFen(r - 1) - GetFen(l - 1);
        };

        vector < int > Rs(q, 0);
        for (int i = 0; i < n; i ++)
        {
                AddFen(dec[i], 1);
                for (auto e : Qvent[i])
                {
                        int qid = e.first;
                        Rs[qid] += GetFenLR(la[qid], ra[qid]) * e.second;
                }
        }
        for (int i = 0; i < q; i ++)
                if (Rs[i]) Rs[i] = 1;
        return Rs;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from werewolf.cpp:2:
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:62:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         assert(vec.size() == n);
      |                ~~~~~~~~~~~^~~~
werewolf.cpp:85:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         assert(dec.size() == n);
      |                ~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51