oj.uz

답안 #794736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794736 2023-07-26T21:08:20 Z IvanJ 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1043 ms 192944 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;

int n, m, q;
int ans[maxn];
vector<int> graph[maxn];
vector<pair<ii, int>> qL[maxn], qR[maxn];

struct Tree {
	int sz, dt;
	vector<vector<int>> adj, anc;
	vector<int> par, pos, l, r;
	vector<int> perm, vis;
	
	void init(int _sz) {
		sz = _sz;
		for(int i = 0;i < sz;i++) 
			adj.pb({}), par.pb(i), pos.pb(-1), vis.pb(0);
	}
	
	int find(int x) {return (x == par[x]) ? x : par[x] = find(par[x]);}
	
	void add(int v) {
		int x = sz++;
		adj.pb({}), par.pb(x);
		pos[v] = x, vis[v] = 1;
		adj[x].pb(find(v));
		vector<int> a;
		a.pb(v);
		for(int y : graph[v]) 
			if(vis[y]) adj[x].pb(find(y)), a.pb(y);
		for(int i : a) par[find(i)] = x;
		adj[x].resize(unique(all(adj[x])) - adj[x].begin());
	}
	
	void dfs(int x) {
		l[x] = dt;
		for(int i = 1;i < 20;i++) 
			anc[x][i] = anc[anc[x][i - 1]][i - 1];
		for(int y : adj[x]) anc[y][0] = x, dfs(y);
		r[x] = dt - 1;
		if(x < n) perm.pb(x), dt++;
	}
	
	void build() {
		dt = 0;
		adj.pb({});
		for(int i = 0;i < sz;i++) 
			if(par[i] == i) adj[sz].pb(i);
		sz++;
		vector<int> V(20, sz - 1);
		for(int i = 0;i < sz;i++) 
			l.pb(0), r.pb(0), anc.pb(V);
		dfs(sz - 1);
	}
	
	ii get_range(int x, int y) {
		for(int i = 19;i >= 0;i--) {
			if(anc[x][i] <= pos[y]) 
				x = anc[x][i];
		}
		return {l[x], r[x]};
	}
} H, W;

struct bit {
	int sz;
	vector<int> fwt;
	void init(int _sz) {
		sz = _sz + 1;
		for(int i = 0;i < sz;i++) fwt.pb(0);
	}
	
	void update(int x) {x++;for(;x < sz;x += (x & -x)) fwt[x]++;}
	
	int query(int x) {
		x++;
		int ret = 0;
		for(;x > 0;x -= (x & -x)) ret += fwt[x];
		return ret;
	}
	
	int get(int lo, int hi) {return query(hi) - query(lo - 1);}
} DS;

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, m = (int)X.size(), q = (int)S.size();
	for(int i = 0;i < m;i++) 
		graph[X[i]].pb(Y[i]), graph[Y[i]].pb(X[i]);

	H.init(n), W.init(n);
	for(int i = 0;i < n;i++) 
		W.add(i), H.add(n - i - 1);
	
	H.build(), W.build();
	
	for(int i = 0;i < q;i++) {
		ii r1 = H.get_range(S[i], L[i]);
		ii r2 = W.get_range(E[i], R[i]);
		qL[r2.x].pb({r1, i}), qR[r2.y].pb({r1, i});
	}
	
	vector<int> p;
	vector<int> pos(n, 0);
	for(int i = 0;i < n;i++) pos[H.perm[i]] = i;
	for(int i = 0;i < n;i++) p.pb(pos[W.perm[i]]);

	DS.init(n);
	for(int i = 0;i < n;i++) {
		for(auto r : qL[i]) {
			int lo = r.x.x, hi = r.x.y;
			int cnt = DS.get(lo, hi);
			ans[r.y] -= cnt;
		}
		DS.update(p[i]);
		for(auto r : qR[i]) {
			int lo = r.x.x, hi = r.x.y;
			int cnt = DS.get(lo, hi);
			ans[r.y] += cnt;
		}
	}
	
	vector<int> ret;
	for(int i = 0;i < q;i++) ret.pb(ans[i] > 0);
	return ret;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 964 ms 183124 KB Output is correct
2 Correct 932 ms 192856 KB Output is correct
3 Correct 810 ms 191376 KB Output is correct
4 Correct 769 ms 190796 KB Output is correct
5 Correct 788 ms 190672 KB Output is correct
6 Correct 915 ms 190992 KB Output is correct
7 Correct 894 ms 189868 KB Output is correct
8 Correct 826 ms 192900 KB Output is correct
9 Correct 755 ms 191568 KB Output is correct
10 Correct 702 ms 189556 KB Output is correct
11 Correct 662 ms 190664 KB Output is correct
12 Correct 730 ms 190488 KB Output is correct
13 Correct 1043 ms 192660 KB Output is correct
14 Correct 1037 ms 192772 KB Output is correct
15 Correct 1006 ms 192720 KB Output is correct
16 Correct 1012 ms 192944 KB Output is correct
17 Correct 984 ms 190036 KB Output is correct

Subtask #4
0 / 51.0

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