oj.uz

답안 #1010469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010469 2024-06-29T06:36:36 Z Muaath_5 늑대인간 (IOI18_werewolf) C++17
15 / 100
 1378 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<<19, 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 << 19, C = 1 << 19;
 
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 66 ms 148312 KB Output is correct
2 Correct 116 ms 148308 KB Output is correct
3 Correct 68 ms 148152 KB Output is correct
4 Correct 86 ms 148052 KB Output is correct
5 Correct 97 ms 148308 KB Output is correct
6 Correct 97 ms 148336 KB Output is correct
7 Correct 65 ms 148304 KB Output is correct
8 Correct 85 ms 148304 KB Output is correct
9 Correct 75 ms 148112 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 148312 KB Output is correct
2 Correct 116 ms 148308 KB Output is correct
3 Correct 68 ms 148152 KB Output is correct
4 Correct 86 ms 148052 KB Output is correct
5 Correct 97 ms 148308 KB Output is correct
6 Correct 97 ms 148336 KB Output is correct
7 Correct 65 ms 148304 KB Output is correct
8 Correct 85 ms 148304 KB Output is correct
9 Correct 75 ms 148112 KB Output is correct
10 Correct 99 ms 158784 KB Output is correct
11 Correct 95 ms 158180 KB Output is correct
12 Correct 87 ms 156244 KB Output is correct
13 Correct 85 ms 159536 KB Output is correct
14 Correct 111 ms 159696 KB Output is correct
15 Correct 100 ms 157780 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 148312 KB Output is correct
2 Correct 116 ms 148308 KB Output is correct
3 Correct 68 ms 148152 KB Output is correct
4 Correct 86 ms 148052 KB Output is correct
5 Correct 97 ms 148308 KB Output is correct
6 Correct 97 ms 148336 KB Output is correct
7 Correct 65 ms 148304 KB Output is correct
8 Correct 85 ms 148304 KB Output is correct
9 Correct 75 ms 148112 KB Output is correct
10 Correct 99 ms 158784 KB Output is correct
11 Correct 95 ms 158180 KB Output is correct
12 Correct 87 ms 156244 KB Output is correct
13 Correct 85 ms 159536 KB Output is correct
14 Correct 111 ms 159696 KB Output is correct
15 Correct 100 ms 157780 KB Output is correct
16 Runtime error 1378 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -