Submission #329332

#	Time	Username	Problem	Language	Result	Execution time	Memory
329332		figter001	Werewolf (IOI18_werewolf)	C++17	15 / 100	2776 ms	524292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

vector<vector<int>> g,atj;
int n;

struct Event{
	int s,e,l,r;
	int id;
	pair<int,int> per;
	Event(int A,int B,int C,int D,int E){
		s = A;
		e = B;
		l = C;
		r = D;
		id = E;
	}
};

vector<int> dsu;
vector<vector<int>> fr,to;
int T;

void addEdge(int u,int v){
	g[u].push_back(v);
	g[v].push_back(u);
}

int To;

void init(int n,int x){
	dsu = vector<int> (2*n+x);
	T = 0;
	g.clear();
	g.resize(2*n);
	To = n;
	iota(dsu.begin()+x,dsu.end(),x);
}

int find(int u){
	return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}

void merge(int u,int v){
	u = find(u);
	v = find(v);
	if(u == v)return;
	addEdge(u,To);
	addEdge(v,To);
	// cerr << u << ' '  << v << ' ' << To << '\n';
	dsu[v] = To;
	dsu[u] = To;
	To++;
}

void dfs(int u,int p,bool t){
	fr[t][u] = ++T;
	// cerr << "- " << t << ' ' << u << '\n';
	for(int v : g[u]){
		if(v == p)continue;
		dfs(v,u,t);
	}
	to[t][u] = T;
}

int p,q;
struct node{
	node *l,*r;
	ll val;
	node(){
		l = r = NULL;
		val = 0;
	}
	void marge(){
		if(l == NULL && r == NULL)return;
		else if(l == NULL)val = r->val;
		else if(r == NULL)val = l->val;
		else val = l->val + r->val;
	}
};

struct node2d{
	node2d *l,*r;
	node *child;
	node2d(){
		l = r = NULL;
		child = new node();
	}
};

node2d *head2d;

void update_range(int at,ll val,node *&n,int s = 1,int e = ::n*2){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;
	// cerr << at << ' ' << s << ' ' << e << '\n';
	if(s == e){
		n->val++;
		return;
	}
	update_range(at , val , n->l , s , (s+e)/2);
	update_range(at , val , n->r , (s+e)/2+1 , e);
	n->marge();
	// cerr << at << ' ' << s << ' ' << e << '\n';
}

ll get(int l,int r,node *&n,int s = 1,int e = ::n*2){
	if(n == NULL)return 0;
	if(s > r || e < l || l > r)return 0LL;
	if(s >= l && e <= r)return n->val;
	ll a = get(l , r , n->l , s , (s+e) / 2);
	ll b = get(l , r , n->r , (s+e)/2+1 , e);
	return a+b;
}

void update_range_2(int at,node *&n,node *&l , node*&r,int s = 1,int e = ::n*2){
	// cerr << at << ' ' << s << ' ' << e << ' ' << (r == NULL) << '\n';
	if(l == NULL && r == NULL)return;
	// cerr << at << ' ' << s << ' ' << e << '\n';
	if(s > at || e < at)return;	
	if(n == NULL)n = new node();
	if(s == e){
		if(l == NULL)n->val = r->val;
		else if(r == NULL)n->val = l->val;
		else n->val = (l->val+r->val);
		return;
	}
	int md = (s+e)/2;
	if(l == NULL){
		update_range_2(at , n->l,l,r->l , s , md);
		update_range_2(at , n->r,l,r->r , md+1 , e);	
	}else if(r == NULL){
		update_range_2(at , n->l,l->l,r , s , md);
		update_range_2(at , n->r,l->r,r , md+1 , e);
	}else{
		update_range_2(at , n->l,l->l,r->l , s , md);
		update_range_2(at , n->r,l->r,r->r , md+1 , e);
	}
	n->marge();
}

void update_range_2d(int at,ll val,node2d *&n = head2d,int s = 1,int e = ::n*2){
	if(s > at || e < at)return;
	if(n == NULL)n = new node2d();
	if(s == e){
		update_range(p,val,n->child);
		return;
	}
	update_range_2d(at , val , n->l , s , (s+e)/2);
	update_range_2d(at , val , n->r , (s+e)/2+1 , e);
	// cerr << at << ' ' << s << ' ' << e << '\n';
	// assert(n->l != NULL);
	// assert(n->r != NULL);
	node *x = new node();
	if(n->l == NULL && n->r == NULL){}
	else if(n->l == NULL)update_range_2(p,n->child,x,n->r->child);
	else if(n->r == NULL)update_range_2(p,n->child,n->l->child,x);
	else update_range_2(p,n->child,n->l->child,n->r->child);
	// cerr << at << ' ' << s << ' ' << e << '\n';
}

ll get_2d(int l,int r,node2d *& n = head2d,int s = 1,int e = ::n*2){
	if(n == NULL)return 0;
	if(s > r || e < l || l > r)return 0LL;
	if(s >= l && e <= r){
		return get(p,q,n->child);
	}
	ll a = get_2d(l , r , n->l , s , (s+e) / 2);
	ll b = get_2d(l , r , n->r , (s+e)/2+1 , e);
	return a+b;
}


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;
	vector<Event> e;
	atj.resize(n);
	for(int i=0;i<x.size();i++){
		atj[x[i]].push_back(y[i]);
		atj[y[i]].push_back(x[i]);
	}
	fr = to = vector<vector<int>>(2,vector<int>(2*n));
	for(int i=0;i<S.size();i++){
		e.push_back(Event(S[i] , E[i] , L[i] , R[i] , i));
	}
	{//Build X axis
		init(n,0);
		sort(all(e) , [](Event a,Event b){
			return a.l > b.l;
		});
		int u = n-1;
		for(int i=0;i<e.size();i++){
			for(;u>=e[i].l;u--){
				for(int v : atj[u]){
					if(v > u)
						merge(u,v);
				}
			}
			e[i].per.first = find(e[i].s);
		}
		for(;u>=0;u--){
			for(int v : atj[u]){
				if(v > u)
					merge(u,v);
			}
		}
		dfs(To-1,-1,0);

	}

	{//Build Y axis
		init(n,0);
		sort(all(e) , [](Event a,Event b){
			return a.r < b.r;
		});
		int u = 0;
		for(int i=0;i<e.size();i++){
			for(;u<=e[i].r;u++){
				for(int v : atj[u]){
					if(v < u)
						merge(u,v);
				}
			}
			e[i].per.second = find(e[i].e);
		}
		for(;u<=n-1;u++){
			for(int v : atj[u]){
				if(v < u)
					merge(u,v);
			}
		}
		dfs(To-1,-1,1);
	}
	head2d = new node2d();
	for(int i=0;i<n;i++){
		p = fr[1][i];
		// cerr << i << ' ' << fr[1][i] << ' ' << fr[0][i] << ' ' << 2*n << '\n';
		update_range_2d(fr[0][i],1);
	}
	vector<int> A(S.size() , 0);
	// return {};
	for(int i=0;i<e.size();i++){
		int id = e[i].per.first;
		int id2 = e[i].per.second;
		p = fr[1][id2];
		q = to[1][id2];
		// cerr << i << ' ' << id << ' ' << fr[0][id] << ' ' << to[0][id] << '\n';
		A[e[i].id] = get_2d(fr[0][id] , to[0][id]) > 0;
	}
	// cerr << "WTF\n";


	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:187:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:192:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |  for(int i=0;i<S.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:201:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:226:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:251:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |  for(int i=0;i<e.size();i++){
      |              ~^~~~~~~~~

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