oj.uz

답안 #619214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619214 2022-08-02T10:33:26 Z Vanilla 늑대인간 (IOI18_werewolf) C++17
0 / 100
 802 ms 160160 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
const int lg = 22;
vector <int> ad [maxn];
vector <int> reach [2][maxn * 2];
int dsu [2 * maxn];
int bit [maxn * 2];
int up [2][maxn * 2][lg];
int in [2][maxn * 2];
int val [2][maxn * 2];
int sz [2][maxn * 2];
int ps = 0;

int dad (int x) {
	return dsu[x] = (x == dsu[x] ? x: dad(dsu[x]));
}

void dfs (int t, int u) {
	in[t][u] = ++ps, sz[t][u] = 1;
	for (int v: reach[t][u]) {
		up[t][v][0] = u;
		for (int i = 1; i < lg; i++){
			up[t][v][i] = up[t][up[t][v][i-1]][i-1];
		}
		dfs(t, v);
		sz[t][u]+=sz[t][v];
	}
}

void add (int x, int y) {
	for (; x < maxn; x+=x & -x) bit[x]+=y;
}

int query (int x) {
	int rs = 0;
	for (; x; x-=x & -x) rs+=bit[x];
	return rs;
}

struct event {
	int type; // 1 -> start, 2 -> point, 3 -> end
	int x; // OX
	int l; // OY
	int r; // OY
	int idx;

	inline bool operator < (const event& oth) const {
		if (x == oth.x) return type < oth.type;
		return x < oth.x;
	}
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	int M = X.size(), Q = L.size();
	vector <int> rs (Q);
	for (int i = 0; i < M; i++){
		ad[X[i]].push_back(Y[i]);
		ad[Y[i]].push_back(X[i]);
	}
	iota (dsu, dsu + 2 * maxn, 0);
	int ct0 = N - 1, ct1 = N - 1;
	for (int i = 0; i < N; i++){
		for (int j: ad[i]) {
			if (j > i) continue;
			int p1 = dad(j), p2 = dad(i);
			if (p1 != p2) {
				ct0++;
				reach[0][ct0].push_back(p1);
				reach[0][ct0].push_back(p2);
				val[0][ct0] = i;
				dsu[p1] = dsu[p2] = ct0;
			}
		}
	}
	iota (dsu, dsu + 2 * maxn, 0);
	for (int i = N - 1; i >= 0; i--) {
		for (int j: ad[i]) {
			if (j < i) continue;
			int p1 = dad(j), p2 = dad(i);
			if (p1 != p2) {
				ct1++;
				reach[1][ct1].push_back(p1);
				reach[1][ct1].push_back(p2);
				val[1][ct1] = i;
				dsu[p1] = dsu[p2] = ct1;

			}
		}
	}
	dfs(0, ct0);
	dfs(1, ct1);
	val[1][0] = -1e9;
	val[0][0] = 1e9;
	for (int i = 0; i < Q; i++){
		for (int j = lg - 1; j >= 0; j--){
			if (val[1][up[1][S[i]][j]] >= L[i]) S[i] = up[1][S[i]][j];
			if (val[0][up[0][E[i]][j]] <= R[i]) E[i] = up[0][E[i]][j];
		}
	}
	vector <event> ev;
	for (int i = 0; i < N; i++){
		ev.push_back({2, in[1][i], in[0][i], in[0][i], i});
	}
	for (int i = 0; i < Q; i++){
		ev.push_back({1, in[1][S[i]], 					in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
		ev.push_back({3, in[1][S[i]] + sz[1][S[i]] - 1, in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
	}
	sort(ev.begin(), ev.end());
	for (auto& [t, x, l, r, id]: ev) {
		if (t == 1) {
			rs[id] -= query(r) - query(l - 1);
		}
		else if (t == 2) {
			add(l, 1);
		}
		else {
			rs[id] += query(r) - query(l - 1);
			
		}
	}
	for (int i = 0; i < Q; i++){
		rs[i] = !!rs[i];
	}
	return rs;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25428 KB Output is correct
2 Incorrect 19 ms 25456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25428 KB Output is correct
2 Incorrect 19 ms 25456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25428 KB Output is correct
2 Incorrect 19 ms 25456 KB Output isn't correct
3 Halted 0 ms 0 KB -