제출 #417491

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

werewolf

//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
typedef complex<int> point;
const int nmax = 200005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = 1e9+10;
const int sq = 5000;

int N;

struct {
	int parent[nmax], size[nmax];
	void init(int n){
		for(int i = 1; i <= n;i++){
			parent[i] = i;
			size[i] = 1;
		}
	}
	int par(int nod){
		while(parent[nod] != parent[parent[nod]]){
			parent[nod] = parent[parent[nod]];
		}
		return parent[nod];
	}
	bool same(int x , int y){
		x = par(x);
		y = par(y);
		return x == y;
	}
	void conn(int x , int y){
		x = par(x);
		y = par(y);
		if(size[x] < size[y])swap(x,y);
		parent[y] = x;
		size[x] += size[y];
	}
} dsa, dsb;

vec < int > g1[nmax], g2[nmax];
vec <int> tour1, tour2, rev;
vec < pair < pii , pii > > lil_qs;

int la[nmax],lb[nmax],ra[nmax],rb[nmax];
int tim = 0;

void dfs1(int nod){
	tim ++;
	la[nod] = tim;
	tour1.pb(nod);
	for(int j : g1[nod]){
		dfs1(j);
	}
	ra[nod] = tim;
}

void dfs2(int nod){
	tim ++;
	lb[nod] = tim;
	tour2.pb(nod);
	for(int j : g2[nod]){
		dfs2(j);
	}
	rb[nod] = tim;
}

vec <int> result;

int bit[nmax];

void update(int pos){
	for(;pos <= N; pos += pos&-pos){
		bit[pos]++;
	}
}
int query(int pos){
	int rs = 0;
	for(;pos > 0; pos -= pos&-pos){
		rs += bit[pos];
	}
	return rs;
}

int prb[nmax][22] , pra[nmax][22];

vec <int> check_validity(int n,vec <int> x,vec <int> y,vec <int> s,vec <int> e,vec <int> l,vec <int> r){
	int m = x.size();
	int q = s.size();
	N = n;
	vec < int > g[nmax];
	vec < pair < pii , pii > >  quer;
	for(int i = 0 ; i < q; i++){
		quer.pb({{s[i],e[i]},{l[i],r[i]}});
	}
	for(int i = 0 ;  i < m ;i++){
		x[i] ++;
		y[i] ++;
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);
	}
	dsa.init(n);
	dsb.init(n);

	for(int i = 1; i <= n; i++){
		for(int j : g[i]){
			if(j > i)continue;
			if(dsa.same(i,j))continue;
			g1[i].pb(j);
			pra[j][0] = i;
			dsa.conn(i,j);
		}
	}
	for(int i = n; i > 0; i--){
		for(int j : g[i]){
			if(j < i)continue;
			if(dsb.same(i,j))continue;
			g2[i].pb(j);
			prb[j][0] = i;
			dsb.conn(i,j);
		}
	}
	for(int k = 1; k <= 20; k++){
		for(int i = 1; i <= n; i++){
			pra[i][k] = pra[pra[i][k-1]][k-1];
			prb[i][k] = prb[prb[i][k-1]][k-1];
		}
	}
	tour1.pb(0);
	tour2.pb(0);
	dfs1(1);
	tim = 0;
	dfs2(n);
	rev.resize(n+1);
	for(int i = 1; i <= n; i++){
		rev[tour1[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		tour2[i] = rev[tour2[i]];
	}
	result.resize(q);
	for(int i = 0; i < q; i++){
		pair < pii , pii > qr = quer[i];
		int nod = qr.fr.fr;
		int limit = qr.sc.sc;
		int l, r;
		for(int k = 20 ; k >= 0 ; k--){
			if(pra[nod][k] <= limit){
				nod = pra[nod][k];
			}
		}
		l = la[nod] , r = ra[nod];
		int nod2 = qr.fr.sc;
		int limit2 = qr.sc.fr;
		int l1, r1;
		for(int k = 20; k >= 0; k--){
			if(prb[nod2][k] >= limit2){
				nod2 = prb[nod2][k];
			}
		}
		l1 = lb[nod2] , r1 = rb[nod2];
		lil_qs.pb({{r1,r},{i,1}});
		lil_qs.pb({{r1,l-1},{i,-1}});
		lil_qs.pb({{l1-1,r},{i,-1}});
		lil_qs.pb({{l1-1,l},{i,1}});
	}

	sort(lil_qs.begin(),lil_qs.end());
	int updated = 0, processed = 0;
	for(int i = 1; i <= n; i++){	
		while(lil_qs[processed].fr.fr <= updated){
			pair < pii, pii> qq = lil_qs[processed];
			result[qq.sc.fr] += qq.sc.sc * query(qq.fr.sc);
			processed++;
		}
		update(tour2[i]);
		updated++;
		while(lil_qs[processed].fr.fr <= updated){
			pair < pii, pii> qq = lil_qs[processed];
			result[qq.sc.fr] += qq.sc.sc * query(qq.fr.sc);
			processed++;
		}
	}
	for(int i = 0 ; i < q ; i++){
		result[i] = (result[i] >= 0);
	}
	return result;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51