제출 #502274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502274		MilosMilutinovic	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4066 ms	130012 KiB

werewolf

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51