oj.uz

답안 #502274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502274 2022-01-05T16:56:46 Z MilosMilutinovic 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 130012 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 = 0; x < n; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14452 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 11 ms 14400 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14452 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 11 ms 14400 KB Output is correct
10 Correct 48 ms 16020 KB Output is correct
11 Correct 47 ms 15996 KB Output is correct
12 Correct 44 ms 15956 KB Output is correct
13 Correct 50 ms 16212 KB Output is correct
14 Correct 44 ms 16208 KB Output is correct
15 Correct 42 ms 16144 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4066 ms 130012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14452 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 11 ms 14400 KB Output is correct
10 Correct 48 ms 16020 KB Output is correct
11 Correct 47 ms 15996 KB Output is correct
12 Correct 44 ms 15956 KB Output is correct
13 Correct 50 ms 16212 KB Output is correct
14 Correct 44 ms 16208 KB Output is correct
15 Correct 42 ms 16144 KB Output is correct
16 Execution timed out 4066 ms 130012 KB Time limit exceeded
17 Halted 0 ms 0 KB -