oj.uz

Submission #318799

# Submission time Handle Problem Language Result Execution time Memory
318799 2020-11-03T08:50:43 Z Vladth11 Werewolf (IOI18_werewolf) C++14
100 / 100
 1209 ms 127708 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 200001;
const int INF = 2e9;
const ll MOD = 998244353;
const ll p = 31;
const ll BLOCK = 101;
const ll nr_of_bits = 18;

vector <int> init[NMAX];

class Arbore {
    int parent[NMAX];
    vector <int> v[NMAX];
    int stamp = 0;
public:
        pii timp[NMAX];

    int dp[NMAX][nr_of_bits];
    vector <int> parcurgere;
    int n;
    void Init(int _n) {
        n = _n;
        parcurgere.push_back(0);
        for(int i = 0; i <= n + 1; i++) {
            parent[i] = 0;
        }
    }
    int root(int x) {
        if(parent[x] == 0)
            return x;
        return (parent[x] = root(parent[x]));
    }
    void merge(int a, int b) {
        a = root(a);
        if(a == b)
            return;
        parent[a] = b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    void DFS(int node, int p) {
        timp[node].first = ++stamp;
        dp[node][0] = p;
        parcurgere.push_back(node);
        for(auto x : v[node]) {
            if(x == p)
                continue;
            DFS(x, node);
        }
        timp[node].second = stamp;
    }
    void Precalc() {
        for(int j = 1; j < nr_of_bits; j++) {
            for(int i = 1; i <= n; i++) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
    }
} C, D;

class AIB{
    int aib[NMAX], n;
public:
    void Init(int _n){
        n = _n + 1;
    }
    void update(int x){
        for(int i = x; i < n; i += i&(-i)){
            aib[i]++;
        }
    }
    int query(int x){
        int s = 0;
        for(int i = x; i > 0; i -= i&(-i)){
            s += aib[i];
        }
        return s;
    }
}aib;

vector <pii> queries[NMAX];

vector <int> Compute(int Q) {
    vector <int> rez(Q + 1);
    map <int, int> mp;
    for(int i = 1; i < D.parcurgere.size(); i++){
        mp[D.parcurgere[i]] = i;
        //debug_with_space(D.parcurgere[i]);
    }
    //debug(Q);

    aib.Init(D.n);
    int i;
    for(int i = 1; i <= C.n; i++){
        aib.update(mp[C.parcurgere[i]]);
       // debug(mp[C.parcurgere[i]]);
        for(auto x : queries[i]){
            int c = x.second;
            if(c < 0)
                c = -1;
            else
                c = 1;
            rez[c * x.second] += c * aib.query(x.first);
        }
    }
    for(i = 0; i < Q; i++){
        rez[i] = (rez[i + 1] > 0);
    }
    return rez;
}


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 Q = S.size();
    vector<int> A(Q);
    int i;
    for(i = 0; i < X.size(); i++) {
        init[X[i] + 1].push_back(Y[i] + 1);
        init[Y[i] + 1].push_back(X[i] + 1);
    }
    C.Init(N);
    D.Init(N);
    for(int i = N; i >= 1; i--) {
        for(auto x : init[i]) {
            if(x > i) {
                C.merge(x, i);
               // break;
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        for(auto x : init[i]) {
            if(x < i) {
                D.merge(x, i);
               // break;
            }
        }
    }
    C.DFS(1, 0);
    //debug(N);
    D.DFS(N, 0);
    C.Precalc();
    D.Precalc();
    for(i = 0; i < Q; i++) {
        S[i]++;
        R[i]++;
        E[i]++;
        L[i]++;
        int r = S[i], pas = nr_of_bits - 1;
        while(pas >= 0) {
            int nou = C.dp[r][pas];
            if(nou != 0 && nou >= L[i])
                r = nou;
            pas--;
        }
        pii a = {C.timp[r].first, C.timp[r].second};
        r = E[i], pas = nr_of_bits - 1;
        while(pas >= 0) {
            int nou = D.dp[r][pas];
            if(nou != 0 && nou <= R[i])
                r = nou;
            pas--;
        }
        pii b = {D.timp[r].first, D.timp[r].second};
        int x1 = a.first, x2 = a.second, y1 = b.first, y2 = b.second;
        queries[x1 - 1].push_back({y1 - 1, i + 1});
        queries[x1 - 1].push_back({y2, -i - 1});
        queries[x2].push_back({y2, i + 1});
        queries[x2].push_back({y1 - 1, -i - 1});
    }
    A = Compute(Q);
    A.pop_back();
    return A;
}
/*
namespace {

int read_int() {
    int x;
    if (scanf("%d", &x) != 1) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    return x;
}

}  // namespace

int main() {
    int N = read_int();
    int M = read_int();
    int Q = read_int();
    vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
    for (int j = 0; j < M; ++j) {
        X[j] = read_int();
        Y[j] = read_int();
    }
    for (int i = 0; i < Q; ++i) {
        S[i] = read_int();
        E[i] = read_int();
        L[i] = read_int();
        R[i] = read_int();
    }
    vector<int> A = check_validity(N, X, Y, S, E, L, R);
    for (size_t i = 0; i < A.size(); ++i) {
        printf("%d\n", A[i]);
    }
    return 0;
}
*/

Compilation message

werewolf.cpp: In function 'std::vector<int> Compute(int)':
werewolf.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 1; i < D.parcurgere.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
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:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(i = 0; i < X.size(); i++) {
      |                ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25452 KB Output is correct
2 Correct 17 ms 25452 KB Output is correct
3 Correct 17 ms 25452 KB Output is correct
4 Correct 17 ms 25452 KB Output is correct
5 Correct 17 ms 25452 KB Output is correct
6 Correct 17 ms 25452 KB Output is correct
7 Correct 17 ms 25452 KB Output is correct
8 Correct 17 ms 25452 KB Output is correct
9 Correct 17 ms 25452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25452 KB Output is correct
2 Correct 17 ms 25452 KB Output is correct
3 Correct 17 ms 25452 KB Output is correct
4 Correct 17 ms 25452 KB Output is correct
5 Correct 17 ms 25452 KB Output is correct
6 Correct 17 ms 25452 KB Output is correct
7 Correct 17 ms 25452 KB Output is correct
8 Correct 17 ms 25452 KB Output is correct
9 Correct 17 ms 25452 KB Output is correct
10 Correct 24 ms 26860 KB Output is correct
11 Correct 24 ms 26860 KB Output is correct
12 Correct 24 ms 26860 KB Output is correct
13 Correct 24 ms 27108 KB Output is correct
14 Correct 23 ms 26980 KB Output is correct
15 Correct 25 ms 26988 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1096 ms 115548 KB Output is correct
2 Correct 867 ms 120024 KB Output is correct
3 Correct 783 ms 115156 KB Output is correct
4 Correct 786 ms 113368 KB Output is correct
5 Correct 820 ms 113496 KB Output is correct
6 Correct 968 ms 115596 KB Output is correct
7 Correct 980 ms 112380 KB Output is correct
8 Correct 851 ms 119892 KB Output is correct
9 Correct 678 ms 113356 KB Output is correct
10 Correct 654 ms 113236 KB Output is correct
11 Correct 687 ms 112984 KB Output is correct
12 Correct 784 ms 111836 KB Output is correct
13 Correct 962 ms 118848 KB Output is correct
14 Correct 969 ms 118736 KB Output is correct
15 Correct 956 ms 118740 KB Output is correct
16 Correct 951 ms 118720 KB Output is correct
17 Correct 968 ms 112100 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25452 KB Output is correct
2 Correct 17 ms 25452 KB Output is correct
3 Correct 17 ms 25452 KB Output is correct
4 Correct 17 ms 25452 KB Output is correct
5 Correct 17 ms 25452 KB Output is correct
6 Correct 17 ms 25452 KB Output is correct
7 Correct 17 ms 25452 KB Output is correct
8 Correct 17 ms 25452 KB Output is correct
9 Correct 17 ms 25452 KB Output is correct
10 Correct 24 ms 26860 KB Output is correct
11 Correct 24 ms 26860 KB Output is correct
12 Correct 24 ms 26860 KB Output is correct
13 Correct 24 ms 27108 KB Output is correct
14 Correct 23 ms 26980 KB Output is correct
15 Correct 25 ms 26988 KB Output is correct
16 Correct 1096 ms 115548 KB Output is correct
17 Correct 867 ms 120024 KB Output is correct
18 Correct 783 ms 115156 KB Output is correct
19 Correct 786 ms 113368 KB Output is correct
20 Correct 820 ms 113496 KB Output is correct
21 Correct 968 ms 115596 KB Output is correct
22 Correct 980 ms 112380 KB Output is correct
23 Correct 851 ms 119892 KB Output is correct
24 Correct 678 ms 113356 KB Output is correct
25 Correct 654 ms 113236 KB Output is correct
26 Correct 687 ms 112984 KB Output is correct
27 Correct 784 ms 111836 KB Output is correct
28 Correct 962 ms 118848 KB Output is correct
29 Correct 969 ms 118736 KB Output is correct
30 Correct 956 ms 118740 KB Output is correct
31 Correct 951 ms 118720 KB Output is correct
32 Correct 968 ms 112100 KB Output is correct
33 Correct 1180 ms 116572 KB Output is correct
34 Correct 360 ms 61768 KB Output is correct
35 Correct 1209 ms 119256 KB Output is correct
36 Correct 1144 ms 115680 KB Output is correct
37 Correct 1207 ms 118500 KB Output is correct
38 Correct 1166 ms 116440 KB Output is correct
39 Correct 1066 ms 127708 KB Output is correct
40 Correct 1085 ms 118560 KB Output is correct
41 Correct 1041 ms 116056 KB Output is correct
42 Correct 909 ms 111712 KB Output is correct
43 Correct 1200 ms 121688 KB Output is correct
44 Correct 1144 ms 118232 KB Output is correct
45 Correct 880 ms 125276 KB Output is correct
46 Correct 928 ms 126804 KB Output is correct
47 Correct 963 ms 118484 KB Output is correct
48 Correct 955 ms 118352 KB Output is correct
49 Correct 968 ms 118216 KB Output is correct
50 Correct 961 ms 118232 KB Output is correct
51 Correct 1027 ms 119512 KB Output is correct
52 Correct 1024 ms 119252 KB Output is correct