oj.uz

Submission #502261

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

using namespace std;

const int MX = 200001;

int n, par[MX][2];
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];
}

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);
    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];
        while (par[s][0] >= l && par[s][0] != s) s = par[s][0];
        while (par[e][1] <= r && par[e][1] != e) e = par[e][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:70: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]
   70 |         while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void BuildLarge()':
werewolf.cpp:132: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]
  132 |         while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 10 ms 14404 KB Output is correct
4 Correct 9 ms 14384 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 10 ms 14396 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 10 ms 14404 KB Output is correct
4 Correct 9 ms 14384 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 10 ms 14396 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct
10 Correct 34 ms 15044 KB Output is correct
11 Correct 37 ms 14916 KB Output is correct
12 Correct 28 ms 14916 KB Output is correct
13 Correct 30 ms 15252 KB Output is correct
14 Correct 31 ms 15232 KB Output is correct
15 Correct 41 ms 15220 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 10 ms 14404 KB Output is correct
4 Correct 9 ms 14384 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 8 ms 14400 KB Output is correct
8 Correct 10 ms 14396 KB Output is correct
9 Correct 8 ms 14400 KB Output is correct
10 Correct 34 ms 15044 KB Output is correct
11 Correct 37 ms 14916 KB Output is correct
12 Correct 28 ms 14916 KB Output is correct
13 Correct 30 ms 15252 KB Output is correct
14 Correct 31 ms 15232 KB Output is correct
15 Correct 41 ms 15220 KB Output is correct
16 Execution timed out 4046 ms 46056 KB Time limit exceeded
17 Halted 0 ms 0 KB -