oj.uz

답안 #1029763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029763 2024-07-21T09:40:38 Z DorostWef 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 133836 KB 
/* In the name of GOD */

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
const int N = 200012;
vector <int> g[N], t[2][N * 2];
int p[N * 2];
int par[2][N * 2];
int q;
int n;
int m;
int sz = N;
bool vis[N * 2];

void clear () {
	sz = N;
	for (int i = 0; i < N * 2; i++) 
		p[i] = i;
}

int get_par (int v) {
	return (p[v] == v ? v : p[v] = get_par (p[v]));
}

void merge (int u, int v, int i) {
	u = get_par (u);
	v = get_par (v);
	if (u == v)
		return;
	sz++;
	p[u] = sz;
	p[v] = sz;
	t[i][sz].push_back(v);
	t[i][sz].push_back(u);
}

struct que {
	int s, e, l, r;
	int v1, v2;
} qu[N];

vector <int> ll[N], rr[N];
int st [2][N * 2], ft [2][N * 2];
int ti = 1;

void dfs (int v, int i) {
	vis[v] = true;
	st[i][v] = ti;
	for (int u : t[i][v])
		dfs (u, i);
	if (v < N)
		ti++;
	ft[i][v] = ti;
}

const int SegN = N * 4;
vector <int> seg[SegN];
int aa[N];

void build (int v = 1, int tl = 0, int tr = n - 1) {
	if (tl == tr) {
		seg[v] = {aa[tl]};
		return;
	}
	int mid = (tl + tr) >> 1;
	build (v << 1, tl, mid);
	build (v << 1 | 1, mid + 1, tr);
	merge(seg[v << 1].begin(), seg[v << 1].end(), seg[v << 1 | 1].begin(), seg[v << 1 | 1].end(), back_inserter(seg[v]));
}

int get (int l, int r, int s, int e, int v = 1, int tl = 0, int tr = n - 1) {
	if (l > tr || tl > r)
		return 0;
	if (l <= tl && tr <= r) {
		if (lower_bound(seg[v].begin(), seg[v].end(), s) == upper_bound (seg[v].begin(), seg[v].end(), e)) {
			return 0;
		}
		return 1;
	}
	int mid = (tl + tr) >> 1;
	return get (l, r, s, e, v << 1, tl, mid) | get (l, r, s, e, v << 1 | 1, mid + 1, tr);
}

std::vector<int> check_validity(int NN, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    q = S.size();
    n = NN;
    m = X.size();
	for (int i = 0; i < m; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for (int i = 0; i < q; i++) {
		qu[i].s = S[i];
		qu[i].e = E[i];
		qu[i].l = L[i];
		qu[i].r = R[i];
		ll[L[i]].push_back(i);
		rr[R[i]].push_back(i);
	}
	clear();
	for (int i = 0; i < n; i++) {
		for (int j : g[i]) {
			if (j < i)
				merge (i, j, 0);
		}
		for (int j : rr[i]) {
			qu[j].v1 = get_par (qu[j].e);
		}
	}
	clear();
	for (int i = n - 1; i >= 0; i--) {
		for (int j : g[i]) 
			if (j > i)
				merge (i, j, 1);
		for (int j : ll[i]) {
			qu[j].v2 = get_par (qu[j].s);
		}
	}
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[0][i].empty()) {
			dfs (i, 0);
		}
	}
	ti = 1;
	for (int i = 0; i < 2 * N; i++)
		vis[i] = false;
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[1][i].empty()) {
			dfs (i, 1);
		}
	}
	for (int i = 0; i < 2 * N; i++) {
		ft[0][i]--;
		ft[1][i]--;
	}
	for (int i = 0; i < n; i++)
		aa[st[0][i]] = st[1][i];
	build ();
	vector <int> wef;
	for (int i = 0; i < q; i++) {
		int f = 0;
		for (int j = st[0][qu[i].v1]; j <= ft[0][qu[i].v1]; j++) {
			if (aa[j] >= st[1][qu[i].v2] && aa[j] <= ft[1][qu[i].v2])
				f = 1;
		}
		wef.push_back(f);
//		wef.push_back(get (st[0][qu[i].v1], ft[0][qu[i].v1], st[1][qu[i].v2], ft[1][qu[i].v2]));
	}
	return wef;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 57180 KB Output is correct
2 Correct 25 ms 57176 KB Output is correct
3 Correct 25 ms 57180 KB Output is correct
4 Correct 26 ms 57180 KB Output is correct
5 Correct 25 ms 57180 KB Output is correct
6 Correct 26 ms 57172 KB Output is correct
7 Correct 25 ms 57176 KB Output is correct
8 Correct 25 ms 57180 KB Output is correct
9 Correct 24 ms 57180 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 57180 KB Output is correct
2 Correct 25 ms 57176 KB Output is correct
3 Correct 25 ms 57180 KB Output is correct
4 Correct 26 ms 57180 KB Output is correct
5 Correct 25 ms 57180 KB Output is correct
6 Correct 26 ms 57172 KB Output is correct
7 Correct 25 ms 57176 KB Output is correct
8 Correct 25 ms 57180 KB Output is correct
9 Correct 24 ms 57180 KB Output is correct
10 Correct 38 ms 58460 KB Output is correct
11 Correct 39 ms 58204 KB Output is correct
12 Correct 29 ms 58204 KB Output is correct
13 Correct 39 ms 58448 KB Output is correct
14 Correct 40 ms 58508 KB Output is correct
15 Correct 31 ms 58460 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 395 ms 128500 KB Output is correct
2 Execution timed out 4062 ms 133836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 57180 KB Output is correct
2 Correct 25 ms 57176 KB Output is correct
3 Correct 25 ms 57180 KB Output is correct
4 Correct 26 ms 57180 KB Output is correct
5 Correct 25 ms 57180 KB Output is correct
6 Correct 26 ms 57172 KB Output is correct
7 Correct 25 ms 57176 KB Output is correct
8 Correct 25 ms 57180 KB Output is correct
9 Correct 24 ms 57180 KB Output is correct
10 Correct 38 ms 58460 KB Output is correct
11 Correct 39 ms 58204 KB Output is correct
12 Correct 29 ms 58204 KB Output is correct
13 Correct 39 ms 58448 KB Output is correct
14 Correct 40 ms 58508 KB Output is correct
15 Correct 31 ms 58460 KB Output is correct
16 Correct 395 ms 128500 KB Output is correct
17 Execution timed out 4062 ms 133836 KB Time limit exceeded
18 Halted 0 ms 0 KB -