oj.uz

Submission #742213

# Submission time Handle Problem Language Result Execution time Memory
742213 2023-05-15T20:08:29 Z Ronin13 Werewolf (IOI18_werewolf) C++14
100 / 100
 661 ms 94020 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 200001;

/*6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
vector <int> p(nmax);

void make_set(int v){
    p[v]= v;

}

int find_set(int v){
    return p[v] == v ? v : p[v] = find_set(p[v]);
}

vector <int> g[nmax][2];

void union_sets(int a, int b, int ind){
    a = find_set(a);
    b = find_set(b);
    if(a == b)
        return;
    p[b] = a;
    g[a][ind].pb(b);
}

vector <int> eu[2];
int in[nmax][2], sz[nmax][2];
int timer = 1;

void dfs(int v, int e, int ind){
    eu[ind].pb(v);
    in[v][ind] = timer++;
    sz[v][ind] = 1;
    for(int to : g[v][ind]){
        if(to != e)
            dfs(to, v, ind), sz[v][ind] += sz[to][ind];
    }
}

int t[4 * nmax];



void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = min(t[2 * v], t[2 * v+ 1]);
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 1e9;
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) / 2;
    return min(get(2 * v, l, m, st, fin), get(2 * v + 1, m + 1, r, st, fin));
}

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> l, std::vector<int> r) {
    int q = s.size();
    vector <vector <int> > G(n);
    vector <vector <int> > vec(n);
    vector <int> a(q);
    vector <int> b(q);
    for(int i = 0; i < x.size(); i++){
        int u = x[i], v = y[i];
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i = 0; i < r.size(); i++){
        vec[r[i]].pb(i);
    }
    for(int i = 0; i < n; i++){
        make_set(i);
    }
    for(int i = 0; i < n; i++){
        for(int to : G[i]){
            if(i > to)
                union_sets(i, to, 0);
        }
        for(int to : vec[i]){
            a[to] = find_set(e[to]);
        }
    }

    for(int i = 0; i < n; i++){
        vec[i].clear();
        make_set(i);
    }
    for(int i = 0; i < l.size(); i++){
        vec[l[i]].pb(i);
    }
    for(int i = n - 1; i >= 0; --i){
        for(int to : G[i]){
            if(i < to)
                union_sets(i, to, 1);
        }
        for(int to : vec[i]){
            b[to] = find_set(s[to]);
        }
    }

    eu[0].pb(-1);
    eu[1].pb(-1);
    dfs(n - 1, n - 1,  0);

    timer = 1;
    dfs(0, 0, 1);

    vector <vector <pair<pii, pii> > > qv(n + 1);
    for(int i = 0; i < q; i++){
        int l = in[a[i]][0];
        int r = in[a[i]][0] + sz[a[i]][0] - 1;
        int L = in[b[i]][1];
        int R = in[b[i]][1] + sz[b[i]][1] - 1;
        qv[l].pb({{r, i}, {L, R}});
    }

    for(int i = 1; i <= n; ++i){
        int x = in[eu[1][i]][0];
        update(1, 1, n, i, x);
    }

    vector <int> ans(q);
    for(int i = 1; i <= n; i++){
        for(auto to : qv[i]){
            int r = to.f.f, ind = to.f.s;
            int L = to.s.f, R = to.s.s;
            if(get(1, 1, n, L, R) > r) ans[ind] = 0;
            else ans[ind] = 1;
        }
        update(1, 1, n, in[eu[0][i]][1], 1e9);
    }
    return ans;
}

Compilation message

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: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 = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i < r.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i = 0; i < l.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10532 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 12 ms 11536 KB Output is correct
11 Correct 11 ms 11536 KB Output is correct
12 Correct 9 ms 11476 KB Output is correct
13 Correct 10 ms 11732 KB Output is correct
14 Correct 10 ms 11660 KB Output is correct
15 Correct 12 ms 11592 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 69464 KB Output is correct
2 Correct 598 ms 75308 KB Output is correct
3 Correct 570 ms 78180 KB Output is correct
4 Correct 508 ms 76480 KB Output is correct
5 Correct 577 ms 76412 KB Output is correct
6 Correct 611 ms 76456 KB Output is correct
7 Correct 515 ms 74124 KB Output is correct
8 Correct 520 ms 82312 KB Output is correct
9 Correct 478 ms 77644 KB Output is correct
10 Correct 478 ms 75716 KB Output is correct
11 Correct 464 ms 76224 KB Output is correct
12 Correct 504 ms 76220 KB Output is correct
13 Correct 527 ms 88516 KB Output is correct
14 Correct 547 ms 88604 KB Output is correct
15 Correct 513 ms 88536 KB Output is correct
16 Correct 560 ms 88656 KB Output is correct
17 Correct 504 ms 74452 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10532 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 6 ms 10452 KB Output is correct
10 Correct 12 ms 11536 KB Output is correct
11 Correct 11 ms 11536 KB Output is correct
12 Correct 9 ms 11476 KB Output is correct
13 Correct 10 ms 11732 KB Output is correct
14 Correct 10 ms 11660 KB Output is correct
15 Correct 12 ms 11592 KB Output is correct
16 Correct 579 ms 69464 KB Output is correct
17 Correct 598 ms 75308 KB Output is correct
18 Correct 570 ms 78180 KB Output is correct
19 Correct 508 ms 76480 KB Output is correct
20 Correct 577 ms 76412 KB Output is correct
21 Correct 611 ms 76456 KB Output is correct
22 Correct 515 ms 74124 KB Output is correct
23 Correct 520 ms 82312 KB Output is correct
24 Correct 478 ms 77644 KB Output is correct
25 Correct 478 ms 75716 KB Output is correct
26 Correct 464 ms 76224 KB Output is correct
27 Correct 504 ms 76220 KB Output is correct
28 Correct 527 ms 88516 KB Output is correct
29 Correct 547 ms 88604 KB Output is correct
30 Correct 513 ms 88536 KB Output is correct
31 Correct 560 ms 88656 KB Output is correct
32 Correct 504 ms 74452 KB Output is correct
33 Correct 556 ms 77632 KB Output is correct
34 Correct 278 ms 49760 KB Output is correct
35 Correct 603 ms 81720 KB Output is correct
36 Correct 624 ms 77596 KB Output is correct
37 Correct 581 ms 80564 KB Output is correct
38 Correct 566 ms 78572 KB Output is correct
39 Correct 586 ms 93804 KB Output is correct
40 Correct 647 ms 86508 KB Output is correct
41 Correct 609 ms 78912 KB Output is correct
42 Correct 497 ms 76320 KB Output is correct
43 Correct 661 ms 87900 KB Output is correct
44 Correct 578 ms 80144 KB Output is correct
45 Correct 600 ms 94020 KB Output is correct
46 Correct 580 ms 93544 KB Output is correct
47 Correct 561 ms 88808 KB Output is correct
48 Correct 521 ms 88640 KB Output is correct
49 Correct 557 ms 88756 KB Output is correct
50 Correct 538 ms 88640 KB Output is correct
51 Correct 629 ms 84380 KB Output is correct
52 Correct 589 ms 84444 KB Output is correct