oj.uz

Submission #185430

# Submission time Handle Problem Language Result Execution time Memory
185430 2020-01-11T16:13:44 Z alexandra_udristoiu Werewolf (IOI18_werewolf) C++14
100 / 100
 871 ms 74632 KB 
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include "werewolf.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static int n, q, nr;
static int t[DIM], aint[4 * DIM], d[DIM];
static pair<int, int> p[2][DIM];
static vector<int> v[DIM], vt[2][DIM], sol;
struct str{
    int ind, x, y, st, dr, p1, u1, p2, u2;
};
static str w[DIM];
int cmp1(str a, str b){
    return a.st > b.st;
}
int cmp2(str a, str b){
    return a.dr < b.dr;
}
int cmp3(str a, str b){
    return a.p1 > b.p1;
}
int rad(int x){
    int y, aux;
    y = x;
    while(t[y] != 0){
        y = t[y];
    }
    while(t[x] != 0){
        aux = t[x];
        t[x] = y;
        x = aux;
    }
    return y;
}
void update(int nod, int st, int dr, int p, int val){
    if(st == dr){
        aint[nod] = val;
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, val);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p, val);
        }
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }
}
int query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        return aint[nod];
    }
    else{
        int mid = (st + dr) / 2;
        int x, y;
        x = y = n + 1;
        if(p <= mid){
            x = query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            y = query(2 * nod + 1, mid + 1, dr, p, u);
        }
        return min(x, y);
    }
}
void dfs(int nod, int ind){
    p[ind][nod].f = ++nr;
    for(int i = 0; i < vt[ind][nod].size(); i++){
        dfs(vt[ind][nod][i], ind);
    }
    p[ind][nod].s = nr;
}
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 i, j, nod, u, r;
    n = N;
    q = S.size();
    sol.resize(q);
    for(i = 0; i < X.size(); i++){
        X[i]++; Y[i]++;
        v[ X[i] ].push_back(Y[i]);
        v[ Y[i] ].push_back(X[i]);
    }
    for(i = 0; i < q; i++){
        w[i + 1] = {i, S[i] + 1, E[i] + 1, L[i] + 1, R[i] + 1, 0, 0, 0, 0};
    }
    sort(w + 1, w + q + 1, cmp1);
    u = 1;
    for(i = n; i >= 1; i--){
        for(j = 0; j < v[i].size(); j++){
            nod = v[i][j];
            r = rad(nod);
            if(nod > i && r != i){
                t[r] = i;
                vt[0][i].push_back(r);
            }
        }
        while(w[u].st == i){
            w[u].p1 = rad(w[u].x);
            u++;
        }
    }
    memset(t, 0, sizeof(t) );
    sort(w + 1, w + q + 1, cmp2);
    u = 1;
    for(i = 1; i <= n; i++){
        for(j = 0; j < v[i].size(); j++){
            nod = v[i][j];
            r = rad(nod);
            if(nod < i && r != i){
                t[r] = i;
                vt[1][i].push_back(r);
            }
        }
        while(w[u].dr == i){
            w[u].p2 = rad(w[u].y);
            u++;
        }
    }
    dfs(1, 0);
    nr = 0;
    dfs(n, 1);
    for(i = 1; i <= n; i++){
        d[ p[0][i].f ] = i;
    }
    for(i = 1; i <= q; i++){
        nod = w[i].p1;
        w[i].p1 = p[0][nod].f;
        w[i].u1 = p[0][nod].s;
        nod = w[i].p2;
        w[i].p2 = p[1][nod].f;
        w[i].u2 = p[1][nod].s;
    }
    sort(w + 1, w + q + 1, cmp3);
    u = 1;
    for(i = 1; i <= 4 * n; i++){
        aint[i] = n + 1;
    }
    for(i = n; i >= 1; i--){
        update(1, 1, n, p[1][ d[i] ].f, i);
        while(w[u].p1 == i){
            if( query(1, 1, n, w[u].p2, w[u].u2) <= w[u].u1){
                sol[ w[u].ind ] = 1;
            }
            else{
                sol[ w[u].ind ] = 0;
            }
            u++;
        }
    }
    return sol;
}

Compilation message

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vt[ind][nod].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:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < X.size(); i++){
                ~~^~~~~~~~~~
werewolf.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~
werewolf.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15224 KB Output is correct
2 Correct 17 ms 15224 KB Output is correct
3 Correct 16 ms 15224 KB Output is correct
4 Correct 16 ms 15224 KB Output is correct
5 Correct 16 ms 15240 KB Output is correct
6 Correct 16 ms 15224 KB Output is correct
7 Correct 16 ms 15224 KB Output is correct
8 Correct 16 ms 15224 KB Output is correct
9 Correct 16 ms 15224 KB Output is correct
10 Correct 24 ms 16120 KB Output is correct
11 Correct 23 ms 16024 KB Output is correct
12 Correct 23 ms 15992 KB Output is correct
13 Correct 23 ms 16120 KB Output is correct
14 Correct 23 ms 16120 KB Output is correct
15 Correct 24 ms 16084 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 55000 KB Output is correct
2 Correct 712 ms 58304 KB Output is correct
3 Correct 689 ms 56060 KB Output is correct
4 Correct 695 ms 55032 KB Output is correct
5 Correct 696 ms 55028 KB Output is correct
6 Correct 774 ms 54888 KB Output is correct
7 Correct 683 ms 54892 KB Output is correct
8 Correct 678 ms 58488 KB Output is correct
9 Correct 648 ms 56184 KB Output is correct
10 Correct 623 ms 55136 KB Output is correct
11 Correct 644 ms 55032 KB Output is correct
12 Correct 669 ms 54880 KB Output is correct
13 Correct 673 ms 63992 KB Output is correct
14 Correct 699 ms 63992 KB Output is correct
15 Correct 685 ms 63864 KB Output is correct
16 Correct 682 ms 63864 KB Output is correct
17 Correct 731 ms 55032 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15224 KB Output is correct
2 Correct 17 ms 15224 KB Output is correct
3 Correct 16 ms 15224 KB Output is correct
4 Correct 16 ms 15224 KB Output is correct
5 Correct 16 ms 15240 KB Output is correct
6 Correct 16 ms 15224 KB Output is correct
7 Correct 16 ms 15224 KB Output is correct
8 Correct 16 ms 15224 KB Output is correct
9 Correct 16 ms 15224 KB Output is correct
10 Correct 24 ms 16120 KB Output is correct
11 Correct 23 ms 16024 KB Output is correct
12 Correct 23 ms 15992 KB Output is correct
13 Correct 23 ms 16120 KB Output is correct
14 Correct 23 ms 16120 KB Output is correct
15 Correct 24 ms 16084 KB Output is correct
16 Correct 771 ms 55000 KB Output is correct
17 Correct 712 ms 58304 KB Output is correct
18 Correct 689 ms 56060 KB Output is correct
19 Correct 695 ms 55032 KB Output is correct
20 Correct 696 ms 55028 KB Output is correct
21 Correct 774 ms 54888 KB Output is correct
22 Correct 683 ms 54892 KB Output is correct
23 Correct 678 ms 58488 KB Output is correct
24 Correct 648 ms 56184 KB Output is correct
25 Correct 623 ms 55136 KB Output is correct
26 Correct 644 ms 55032 KB Output is correct
27 Correct 669 ms 54880 KB Output is correct
28 Correct 673 ms 63992 KB Output is correct
29 Correct 699 ms 63992 KB Output is correct
30 Correct 685 ms 63864 KB Output is correct
31 Correct 682 ms 63864 KB Output is correct
32 Correct 731 ms 55032 KB Output is correct
33 Correct 755 ms 63916 KB Output is correct
34 Correct 436 ms 54392 KB Output is correct
35 Correct 783 ms 66804 KB Output is correct
36 Correct 858 ms 64104 KB Output is correct
37 Correct 756 ms 65688 KB Output is correct
38 Correct 778 ms 65048 KB Output is correct
39 Correct 719 ms 74220 KB Output is correct
40 Correct 871 ms 74252 KB Output is correct
41 Correct 735 ms 65228 KB Output is correct
42 Correct 687 ms 64176 KB Output is correct
43 Correct 859 ms 71936 KB Output is correct
44 Correct 745 ms 65592 KB Output is correct
45 Correct 689 ms 74632 KB Output is correct
46 Correct 669 ms 74236 KB Output is correct
47 Correct 681 ms 72440 KB Output is correct
48 Correct 676 ms 72380 KB Output is correct
49 Correct 714 ms 72456 KB Output is correct
50 Correct 689 ms 72288 KB Output is correct
51 Correct 869 ms 74232 KB Output is correct
52 Correct 863 ms 74128 KB Output is correct