oj.uz

Submission #293937

# Submission time Handle Problem Language Result Execution time Memory
293937 2020-09-08T13:51:29 Z Kastanda Werewolf (IOI18_werewolf) C++11
100 / 100
 824 ms 99172 KB 
// 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41088 KB Output is correct
2 Correct 29 ms 41088 KB Output is correct
3 Correct 27 ms 41088 KB Output is correct
4 Correct 27 ms 41088 KB Output is correct
5 Correct 29 ms 41088 KB Output is correct
6 Correct 30 ms 41088 KB Output is correct
7 Correct 28 ms 41120 KB Output is correct
8 Correct 26 ms 41088 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41088 KB Output is correct
2 Correct 29 ms 41088 KB Output is correct
3 Correct 27 ms 41088 KB Output is correct
4 Correct 27 ms 41088 KB Output is correct
5 Correct 29 ms 41088 KB Output is correct
6 Correct 30 ms 41088 KB Output is correct
7 Correct 28 ms 41120 KB Output is correct
8 Correct 26 ms 41088 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct
10 Correct 35 ms 41856 KB Output is correct
11 Correct 35 ms 41848 KB Output is correct
12 Correct 34 ms 41856 KB Output is correct
13 Correct 35 ms 41856 KB Output is correct
14 Correct 31 ms 41856 KB Output is correct
15 Correct 35 ms 41856 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 99172 KB Output is correct
2 Correct 608 ms 85948 KB Output is correct
3 Correct 571 ms 88044 KB Output is correct
4 Correct 670 ms 91116 KB Output is correct
5 Correct 656 ms 92180 KB Output is correct
6 Correct 766 ms 95380 KB Output is correct
7 Correct 649 ms 95480 KB Output is correct
8 Correct 651 ms 86380 KB Output is correct
9 Correct 552 ms 88168 KB Output is correct
10 Correct 569 ms 90604 KB Output is correct
11 Correct 657 ms 91036 KB Output is correct
12 Correct 695 ms 94716 KB Output is correct
13 Correct 650 ms 87836 KB Output is correct
14 Correct 577 ms 87744 KB Output is correct
15 Correct 608 ms 87660 KB Output is correct
16 Correct 598 ms 87908 KB Output is correct
17 Correct 706 ms 95332 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41088 KB Output is correct
2 Correct 29 ms 41088 KB Output is correct
3 Correct 27 ms 41088 KB Output is correct
4 Correct 27 ms 41088 KB Output is correct
5 Correct 29 ms 41088 KB Output is correct
6 Correct 30 ms 41088 KB Output is correct
7 Correct 28 ms 41120 KB Output is correct
8 Correct 26 ms 41088 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct
10 Correct 35 ms 41856 KB Output is correct
11 Correct 35 ms 41848 KB Output is correct
12 Correct 34 ms 41856 KB Output is correct
13 Correct 35 ms 41856 KB Output is correct
14 Correct 31 ms 41856 KB Output is correct
15 Correct 35 ms 41856 KB Output is correct
16 Correct 824 ms 99172 KB Output is correct
17 Correct 608 ms 85948 KB Output is correct
18 Correct 571 ms 88044 KB Output is correct
19 Correct 670 ms 91116 KB Output is correct
20 Correct 656 ms 92180 KB Output is correct
21 Correct 766 ms 95380 KB Output is correct
22 Correct 649 ms 95480 KB Output is correct
23 Correct 651 ms 86380 KB Output is correct
24 Correct 552 ms 88168 KB Output is correct
25 Correct 569 ms 90604 KB Output is correct
26 Correct 657 ms 91036 KB Output is correct
27 Correct 695 ms 94716 KB Output is correct
28 Correct 650 ms 87836 KB Output is correct
29 Correct 577 ms 87744 KB Output is correct
30 Correct 608 ms 87660 KB Output is correct
31 Correct 598 ms 87908 KB Output is correct
32 Correct 706 ms 95332 KB Output is correct
33 Correct 798 ms 95100 KB Output is correct
34 Correct 379 ms 80760 KB Output is correct
35 Correct 773 ms 92908 KB Output is correct
36 Correct 743 ms 95600 KB Output is correct
37 Correct 767 ms 92908 KB Output is correct
38 Correct 744 ms 94828 KB Output is correct
39 Correct 695 ms 94828 KB Output is correct
40 Correct 739 ms 97996 KB Output is correct
41 Correct 626 ms 91756 KB Output is correct
42 Correct 650 ms 92592 KB Output is correct
43 Correct 723 ms 93968 KB Output is correct
44 Correct 668 ms 92268 KB Output is correct
45 Correct 567 ms 91760 KB Output is correct
46 Correct 603 ms 91680 KB Output is correct
47 Correct 604 ms 91704 KB Output is correct
48 Correct 608 ms 91412 KB Output is correct
49 Correct 635 ms 91672 KB Output is correct
50 Correct 587 ms 91444 KB Output is correct
51 Correct 679 ms 95364 KB Output is correct
52 Correct 667 ms 95464 KB Output is correct