oj.uz

Submission #502268

# Submission time Handle Problem Language Result Execution time Memory
502268 2022-01-05T16:40:36 Z MilosMilutinovic Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 130140 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MX = 200001;
const int LG = 25;

int n, par[MX][2], fs[MX][LG], fe[MX][LG];
vector<int> adj[MX], e[MX][2];
vector<pair<int, int>> ed;

struct DSU {
    int fa[MX];
    void init() { iota(fa, fa + MX, 0); }
    DSU() { init(); }
    int root(int x) { return fa[x] == x ? x : fa[x] = root(fa[x]); }
    void unite(int x, int y) { fa[root(x)] = root(y); }
};

void BuildSmall() {
    // 0 is root
    vector<int> fa(n), sz(n), mn(n);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        sz[i] = 1;
        mn[i] = i;
    }
    struct op {
        int root_a;
        int root_b;
        int sz_a;
        int sz_b;
        int mn_a;
        int mn_b;
    };
    stack<op> stk;
    function<int(int)> root = [&](int x) {
        return fa[x] == x ? x : root(fa[x]);
    };
    function<void(int, int)> unite = [&](int x, int y) {
        x = root(x);
        y = root(y);
        if (sz[x] < sz[y]) swap(x, y);
        stk.push({x, y, sz[x], sz[y], mn[x], mn[y]});
        if (x == y) return;
        fa[y] = x;
        sz[x] += sz[y];
        mn[x] = min(mn[x], mn[y]);
    };
    function<void()> roll = [&]() {
        op lst = stk.top();
        stk.pop();
        fa[lst.root_a] = lst.root_a;
        fa[lst.root_b] = lst.root_b;
        sz[lst.root_a] = lst.sz_a;
        sz[lst.root_b] = lst.sz_b;
        mn[lst.root_a] = lst.mn_a;
        mn[lst.root_b] = lst.mn_b;
    };
    sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
        return min(x.first, x.second) < min(y.first, y.second);
    });
    for (int i = ed.size() - 1; i >= 0; i--) {
        unite(ed[i].first, ed[i].second);
    }
    for (int i = 1; i < n; i++)
        par[i][0] = -1;
    int ptr = 0;
    for (int i = 0; i < n; i++) {
        while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
            roll();
            ptr++;
        }
        for (int j : adj[i]) {
            int oth = mn[root(j)];
            if (par[oth][0] == -1) par[oth][0] = i;
        }
    }
}

void BuildLarge() {
    // n-1 is root
    vector<int> fa(n), sz(n), mx(n);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        sz[i] = 1;
        mx[i] = i;
    }
    struct op {
        int root_a;
        int root_b;
        int sz_a;
        int sz_b;
        int mx_a;
        int mx_b;
    };
    stack<op> stk;
    function<int(int)> root = [&](int x) {
        return fa[x] == x ? x : root(fa[x]);
    };
    function<void(int, int)> unite = [&](int x, int y) {
        x = root(x);
        y = root(y);
        if (sz[x] < sz[y]) swap(x, y);
        stk.push({x, y, sz[x], sz[y], mx[x], mx[y]});
        if (x == y) return;
        fa[y] = x;
        sz[x] += sz[y];
        mx[x] = max(mx[x], mx[y]);
    };
    function<void()> roll = [&]() {
        op lst = stk.top();
        stk.pop();
        fa[lst.root_a] = lst.root_a;
        fa[lst.root_b] = lst.root_b;
        sz[lst.root_a] = lst.sz_a;
        sz[lst.root_b] = lst.sz_b;
        mx[lst.root_a] = lst.mx_a;
        mx[lst.root_b] = lst.mx_b;
    };
    sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
        return max(x.first, x.second) > max(y.first, y.second);
    });
    for (int i = ed.size(); i >= 0; i--) {
        unite(ed[i].first, ed[i].second);
    }
    for (int i = 0; i < n - 1; i++)
        par[i][1] = -1;
    par[n - 1][1] = n - 1;
    int ptr = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
            roll();
            ptr++;
        }
        for (int j : adj[i]) {
            int oth = mx[root(j)];
            if (par[oth][1] == -1) par[oth][1] = i;
        }
    }
}

int tin[MX][2], tout[MX][2], tajm[2];

void dfs(int u, int pa, int t) {
    tin[u][t] = ++tajm[t];
    for (int v : e[u][t])
        if (v != pa)
            dfs(v, u, t);
    tout[u][t] = tajm[t];
}

bool is_anc(int x, int y, int t) {
    return tin[x][t] <= tin[y][t] && tout[y][t] <= tout[x][t];
}

const int M = 20 * MX;

int root[MX], ls[M], rs[M], st[M], tsz;

void update(int& c, int p, int ss, int se, int qi) {
    c = ++tsz; ls[c] = ls[p]; rs[c] = rs[p]; st[c] = st[p] + 1;
    if (ss == se) return;
    int mid = ss + se >> 1;
    if (qi <= mid) update(ls[c], ls[p], ss, mid, qi);
    else update(rs[c], rs[p], mid + 1, se, qi);
}

int query(int c, int p, int ss, int se, int qs, int qe) {
    if (ss > qe || se < qs) return 0;
    if (qs <= ss && se <= qe) return st[c] - st[p];
    int mid = ss + se >> 1;
    return query(ls[c], ls[p], ss, mid, qe, se)
         + query(rs[c], rs[p], mid + 1, se, qs, qe);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = N;
    int M = X.size();
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
        ed.emplace_back(X[i], Y[i]);
    }
    BuildSmall();
    BuildLarge();
    /*puts("Small parent");
    for (int i = 0; i < n; i++) cout << par[i][0] << " ";
    puts("Large parent");
    for (int i = 0; i < n; i++) cout << par[i][1] << " ";*/
    for (int i = 1; i < n; i++) {
        e[par[i][0]][0].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        e[par[i][1]][1].push_back(i);
    }
    dfs(0, 0, 0);
    dfs(n - 1, n - 1, 1);
    for (int i = 0; i < n; i++)
        fs[i][0] = par[i][0];
    for (int i = 0; i < n; i++)
        fe[i][0] = par[i][1];
    for (int j = 1; j < LG; j++) {
        for (int i = 0; i < n; i++) {
            fs[i][j] = fs[fs[i][j - 1]][j - 1];
            fe[i][j] = fe[fe[i][j - 1]][j - 1];
        }
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return tin[i][0] < tin[j][0];
    });
    for (int i = 1; i <= n; i++) {
        update(root[i], root[i - 1], 1, n, tin[ord[i - 1]][1]);
    }
    int Q = S.size();
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int l = L[i];
        int r = R[i];
        int s = S[i];
        int e = E[i];
        for (int j = LG - 1; j >= 0; j--) {
            if (fs[s][j] >= l) s = fs[s][j];
            if (fe[e][j] <= r) e = fe[e][j];
        }
        //if (query(root[tout[s][0]], root[tin[s][0] - 1], 1, n, tin[e][1], tout[e][1])) ans[i] = 1;
        for (int x = l; x <= r; x++) {
            if (is_anc(s, x, 0) && is_anc(e, x, 1)) ans[i] = 1;
        }
    }
    return ans;
}

/*
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
*/

Compilation message

werewolf.cpp: In function 'void BuildSmall()':
werewolf.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void BuildLarge()':
werewolf.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void update(int&, int, int, int, int)':
werewolf.cpp:165:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |     int mid = ss + se >> 1;
      |               ~~~^~~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:173:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |     int mid = ss + se >> 1;
      |               ~~~^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 7 ms 14504 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 30 ms 16020 KB Output is correct
11 Correct 32 ms 16008 KB Output is correct
12 Correct 29 ms 15948 KB Output is correct
13 Correct 28 ms 16224 KB Output is correct
14 Correct 26 ms 16204 KB Output is correct
15 Correct 38 ms 16140 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4086 ms 130140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 7 ms 14504 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 30 ms 16020 KB Output is correct
11 Correct 32 ms 16008 KB Output is correct
12 Correct 29 ms 15948 KB Output is correct
13 Correct 28 ms 16224 KB Output is correct
14 Correct 26 ms 16204 KB Output is correct
15 Correct 38 ms 16140 KB Output is correct
16 Execution timed out 4086 ms 130140 KB Time limit exceeded
17 Halted 0 ms 0 KB -