oj.uz

답안 #1010466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010466 2024-06-29T06:35:34 Z Muaath_5 늑대인간 (IOI18_werewolf) C++17
15 / 100
 898 ms 524288 KB 
#include "werewolf.h"
using namespace std;
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define pii pair<int, int>
using namespace std;

const int N = 1<<20, INF = 1e9, LG = 20;

class reachability {
public:
	int sz;
	int dsu[N], par[N];
	vector<int> adj[N];
	reachability(){}
	reachability(int n) {
		sz = n;
		for (int i = 1; i <= n; i++)
			dsu[i] = par[i] = i;
	}
	
	int root(int x) {
		return x == dsu[x] ? x : dsu[x] = root(dsu[x]);
	}
	bool connect(int u, int v) {
		u = root(u), v = root(v);
		if (u == v) return false;
		sz++;
		dsu[u] = dsu[v] = dsu[sz] = sz;
		par[u] = par[v] = par[sz] = sz;
		adj[sz].push_back(u);
		adj[sz].push_back(v); 
		return true;
	}

	
	int jmp[N][LG];
	int dt[N], ft[N];
	int _time;
	int block[N];
    // Maintain minimum/maximum in every subtree
    int mn[N], mx[N];
	void dfsTree() {
        fill(mx, mx+sz+1, -INF);
        fill(mn, mn+sz+1, +INF);
		_time = 1;
		dfs(sz);
	}
	void dfs(int node) {
		dt[node] = _time++;
        if (adj[node].size() == 0)
            mn[node] = mx[node] = node;
		for (int ch : adj[node]) {
			dfs(ch);
            chmin(mn[node], mn[ch]);
            chmax(mx[node], mx[ch]);
        }
		ft[node] = _time-1;
        
	}
    void buildSt() {
        for (int i = 1; i <= sz; i++)
			jmp[i][0] = par[i];
		for (int j = 1; j < LG; j++) {
			for (int i = 1; i <= sz; i++) {
				jmp[i][j] = jmp[jmp[i][j-1]][j-1];
			}
		}
    }
	
	void cutLastEdge() {
		block[sz] = 1;
		sz--;
	}
	
    int findCompLeqMx(int u, int lim) {
        for (int i = LG-1; i >= 0; i--) {
			if (mx[jmp[u][i]] <= lim) {
				u = jmp[u][i];
			}
		}
        return u;
    }

    int findCompGeqMn(int u, int lim) {
        for (int i = LG-1; i >= 0; i--) {
			if (mn[jmp[u][i]] >= lim) {
				u = jmp[u][i];
			}
		}
        return u;
    }

	int findComp(int u) {
		for (int i = LG-1; i >= 0; i--) {
			if (!block[jmp[u][i]]) {
				u = jmp[u][i];
			}
		}
		return u;
	}
};

#define OUT 0ll
int merge(int x, int y) { return x + y; }
 
static int R = 1 << 20, C = 1 << 20;
 
struct ynode {
    int val = OUT;
    ynode *left = nullptr, *right = nullptr;
};
 
struct xnode {
    xnode *left, *right;
    ynode *yy;
};
 
ll query_y(const int& qy1, const int& qy2, ynode* node, int l = 0, int r = C - 1)
{
    if (node == nullptr || r < qy1 || qy2 < l) return OUT;
    if (qy1 <= l && r <= qy2) return node->val;
    const int mid = (l + r) / 2;
    return merge(
        query_y(qy1, qy2, node->left, l, mid),
        query_y(qy1, qy2, node->right, mid + 1, r)
    );
}
 
ll query_x(const int& qx1, const int& qy1, const int& qx2, const int& qy2, xnode* node, int l = 0, int r = R - 1)
{
    if (node == nullptr || r < qx1 || qx2 < l) return OUT;
    if (qx1 <= l && r <= qx2) return query_y(qy1, qy2, node->yy);
    const int mid = (l + r) / 2;
    
    return merge(
        query_x(qx1, qy1, qx2, qy2, node->left, l, mid),
        query_x(qx1, qy1, qx2, qy2, node->right, mid + 1, r)
    );
}
 
 
void update_y(const int& qy, const int& val, ynode* node, int l = 0, int r = C - 1)
{
    if (l == r) {
        node->val = val;
        return;
    }
    const int mid = (l + r) / 2;
    if (qy <= mid) {
        if (!node->left) node->left = new ynode();
        update_y(qy, val, node->left, l, mid);
    }
    else {
        if (!node->right) node->right = new ynode();
        update_y(qy, val, node->right, mid + 1, r);
    }
    ll m1 = OUT, m2 = OUT;
    if (node->left) m1 = node->left->val;
    if (node->right) m2 = node->right->val;
    node->val = merge(m1, m2);
}
 
void update_x(const int& qx, const int& qy, const ll& val, xnode* node, int l = 0, int r = R - 1)
{
    if (!node->yy) node->yy = new ynode();
    if (l == r) {
        update_y(qy, val, node->yy);
        return;
    }
    const int mid = (l + r) / 2;
    if (qx <= mid) {
        if (!node->left) node->left = new xnode();
        update_x(qx, qy, val, node->left, l, mid);
    }
    else {
        if (!node->right) node->right = new xnode();
        update_x(qx, qy, val, node->right, mid + 1, r);
    }
    update_y(qy, merge(
        (node->left && node->left->yy ? query_y(qy, qy, node->left->yy) : OUT),
        (node->right && node->right->yy ? query_y(qy, qy, node->right->yy) : OUT)
    ), node->yy);
}
 
 
xnode* root;
 
void init(int r, int c) { R = r, C = c, root = new xnode(); }
void update(int x, int y, int k) { update_x(x, y, k, root); }
int query(int x1, int y1, int x2, int y2) { return query_x(x1, y1, x2, y2, root); }


vector<int> adj[N];

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    const int M = X.size(), Q = S.size();
    for (int i = 0; i < M; i++)
        X[i]++, Y[i]++;
    for (int i = 0; i < Q; i++)
        S[i]++, E[i]++, L[i]++, R[i]++;

    for (int i = 0; i < M; i++)
        adj[X[i]].push_back(Y[i]),
        adj[Y[i]].push_back(X[i]);

    reachability human(N), werewolf(N);    
    for (int i = 1; i <= N; i++)
        for (int ch : adj[i])
            if (ch <= i)
                werewolf.connect(i, ch);

    for (int i = N; i >= 1; i--)
        for (int ch : adj[i])
            if (ch >= i)
                human.connect(i, ch);



    
    human.dfsTree();human.buildSt();
    werewolf.dfsTree();werewolf.buildSt();
    
    init(human.sz+1, werewolf.sz+1);
    for (int i = 1; i <= N; i++) {
        update(human.dt[i], werewolf.dt[i], 1);
    }
    vector<int> sol(Q);
    for (int i = 0; i < Q; i++) {
        int u = human.findCompGeqMn(S[i], L[i]); // [L...N]
        int v = werewolf.findCompLeqMx(E[i], R[i]); // [1...R]
        sol[i] = !!query(human.dt[u], werewolf.dt[v], human.ft[u], werewolf.ft[v]);
    }
    return sol;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 296024 KB Output is correct
2 Correct 145 ms 296016 KB Output is correct
3 Correct 137 ms 295700 KB Output is correct
4 Correct 138 ms 295688 KB Output is correct
5 Correct 148 ms 295908 KB Output is correct
6 Correct 140 ms 295876 KB Output is correct
7 Correct 140 ms 296020 KB Output is correct
8 Correct 135 ms 296016 KB Output is correct
9 Correct 138 ms 296060 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 296024 KB Output is correct
2 Correct 145 ms 296016 KB Output is correct
3 Correct 137 ms 295700 KB Output is correct
4 Correct 138 ms 295688 KB Output is correct
5 Correct 148 ms 295908 KB Output is correct
6 Correct 140 ms 295876 KB Output is correct
7 Correct 140 ms 296020 KB Output is correct
8 Correct 135 ms 296016 KB Output is correct
9 Correct 138 ms 296060 KB Output is correct
10 Correct 162 ms 306772 KB Output is correct
11 Correct 177 ms 305740 KB Output is correct
12 Correct 155 ms 303956 KB Output is correct
13 Correct 157 ms 307284 KB Output is correct
14 Correct 149 ms 307540 KB Output is correct
15 Correct 173 ms 305512 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 898 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 296024 KB Output is correct
2 Correct 145 ms 296016 KB Output is correct
3 Correct 137 ms 295700 KB Output is correct
4 Correct 138 ms 295688 KB Output is correct
5 Correct 148 ms 295908 KB Output is correct
6 Correct 140 ms 295876 KB Output is correct
7 Correct 140 ms 296020 KB Output is correct
8 Correct 135 ms 296016 KB Output is correct
9 Correct 138 ms 296060 KB Output is correct
10 Correct 162 ms 306772 KB Output is correct
11 Correct 177 ms 305740 KB Output is correct
12 Correct 155 ms 303956 KB Output is correct
13 Correct 157 ms 307284 KB Output is correct
14 Correct 149 ms 307540 KB Output is correct
15 Correct 173 ms 305512 KB Output is correct
16 Runtime error 898 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -