제출 #794734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794734		IvanJ	늑대인간 (IOI18_werewolf)	C++17	0 / 100	462 ms	98588 KiB

werewolf

#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;
	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 y : adj[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++;
		for(int i = 0;i < sz;i++) l.pb(0), r.pb(0);
		dfs(sz - 1);
	}
	
	ii get_range(int x) {
		x = pos[x];
		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]);
		ii r11 = H.get_range(L[i]);
		if(r11.x <= r1.x && r1.y <= r11.y) r1 = r11;
		ii r2 = W.get_range(E[i]);
		ii r22 = W.get_range(R[i]);
		if(r22.x <= r2.x && r2.y <= r22.y) r2 = r22;
		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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51