oj.uz

답안 #568583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568583 2022-05-25T17:53:43 Z ngpin04 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1464 ms 169048 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct DSU {
    int n,node,timer;
    vector <int> par;
    vector <int> tin,tout;
    vector <vector <int>> adj;

    DSU(int _n = 0) {
        n = _n;
        par.assign(2 * n + 5, -1);
        adj.resize(2 * n + 5);
        tin.resize(2 * n + 5);
        tout.resize(2 * n + 5);
        node = n;
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
    }

    void join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return;
        adj[node].push_back(u);
        adj[node].push_back(v);
        par[u] = par[v] = node;
        node++;
    }    

    void dfs(int u) {
        // cerr << "dfs " << u << " " << timer << "\n";
        if (u < n) 
            tin[u] = ++timer;

        for (int v : adj[u]) {
            dfs(v);
            if (!tin[u])
                tin[u] = tin[v];
        }

        tout[u] = timer;
    }

    void build() {
        timer = 0;
        dfs(node - 1);
        for (int i = 0; i < node; i++)
            par[i] = -1;
        node = n;
    }

    pair <int, int> gettree(int u) {
        // cerr << "get tree " << u << " ";
        u = getpar(u);
        // cerr << u << " " << tin[u] << " " << tout[u] << "\n";
        return mp(tin[u], tout[u]);
    }
};

DSU pre, suf;

vector <int> st[N << 2];
vector <int> ed[N];
vector <int> qr[N];


pair <int, int> range[N][2];

int tin[N][2];
int ans[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,q;

void update(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos)
        return;
    st[id].push_back(val);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, pos, val);
    update(id << 1 | 1, mid + 1, r, pos, val);
}

void update(int pos, int val) {
    update(1, 1, n, pos, val);
}

int getans(int id, int l, int r, int u, int v, int x, int y) {
    if (l > v || r < u)
        return 0;
    if (l >= u && r <= v) {
        auto it = lower_bound(ALL(st[id]), x);
        return (it != st[id].end() && *it <= y);
    }
    int mid = (l + r) >> 1;
    int lnode = getans(id << 1, l, mid, u, v, x, y);
    int rnode = getans(id << 1 | 1, mid + 1, r, u, v, x, y);
    return lnode | rnode;
}

int getans(int l, int r, int x, int y) {
    return getans(1, 1, n, l, r, x, y);
}

void build() {
    pre = suf = DSU(n);
    for (int i = 0; i < n - 1; i++) 
        if (x[i] > y[i])
            swap(x[i], y[i]);

    for (int i = 0; i < n - 1; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    for (int i = 0; i < n; i++) 
    for (int j : ed[i])
        pre.join(i, j);
    
    pre.build();

    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) 
            range[ind][0] = pre.gettree(t[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][0] = pre.tin[i];

    // process suffix 
    for (int i = 0; i < n; i++)
        qr[i].clear(), ed[i].clear();

    for (int i = 0; i < n - 1; i++)
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    for (int i = n - 1; i >= 0; i--) 
    for (int j : ed[i])
        suf.join(i, j);

    suf.build();

    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i])
            suf.join(i, j);

        for (int ind : qr[i]) 
            range[ind][1] = suf.gettree(s[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][1] = suf.tin[i];
}  

void solve() {
    for (int i = 0; i < n; i++)
        update(tin[i][0], tin[i][1]);

    for (int i = 1; i <= 4 * n; i++)
        sort(ALL(st[i]));

    for (int i = 0; i < q; i++) {
        int l = range[i][0].fi;
        int r = range[i][0].se;
        int u = range[i][1].fi;
        int v = range[i][1].se;
        // cerr << l << " " << r << " " << u << " " << v << "\n";
        ans[i] = getans(l, r, u, v);
    }
}

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;
    for (int i = 0; i < n - 1; i++)
        x[i] = X[i], y[i] = Y[i];

    q = S.size();
    for (int i = 0; i < q; i++) {
        s[i] = S[i];
        t[i] = E[i];
        l[i] = L[i];
        r[i] = R[i];
    }

    build();
    solve();
    vector <int> res;
    for (int i = 0; i < q; i++)
        res.push_back(ans[i]);
    return res;
}

//#include "grader.cpp"

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 56668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 56668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1344 ms 165156 KB Output is correct
2 Correct 1222 ms 168900 KB Output is correct
3 Correct 1396 ms 166600 KB Output is correct
4 Correct 1210 ms 165552 KB Output is correct
5 Correct 1250 ms 165528 KB Output is correct
6 Correct 1464 ms 165396 KB Output is correct
7 Correct 1278 ms 163888 KB Output is correct
8 Correct 1178 ms 168864 KB Output is correct
9 Correct 1038 ms 166032 KB Output is correct
10 Correct 840 ms 165144 KB Output is correct
11 Correct 878 ms 165200 KB Output is correct
12 Correct 1095 ms 165284 KB Output is correct
13 Correct 873 ms 168912 KB Output is correct
14 Correct 886 ms 169048 KB Output is correct
15 Correct 955 ms 168988 KB Output is correct
16 Correct 896 ms 168960 KB Output is correct
17 Correct 1047 ms 163896 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 56668 KB Output isn't correct
2 Halted 0 ms 0 KB -