Submission #329346

#	Time	Username	Problem	Language	Result	Execution time	Memory
329346		figter001	Werewolf (IOI18_werewolf)	C++17	100 / 100	1640 ms	176964 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 << ' ' << fr[t][u] << '\n';
	for(int v : g[u]){
		if(v == p)continue;
		dfs(v,u,t);
	}
	to[t][u] = T;
}

int p,q;
const int nax = 4e5 + 100;
vector<int> seg[4*nax];
vector<int> val;

void build(int n = 1,int s = 1,int e = ::T){
	if(s == e){
		// cerr << s << ' ' << val[s] << '\n';
		seg[n].push_back(val[s]);
		return;
	}
	build(n+n,s,(s+e)/2);
	build(n+n+1,(s+e)/2+1,e);
	int a=0,b=0;
	seg[n].clear();
	while(a < seg[n+n].size() || b < seg[n+n+1].size()){
		if(a == seg[n+n].size())seg[n].push_back(seg[n+n+1][b++]);
		else if(b == seg[n+n+1].size())seg[n].push_back(seg[n+n][a++]);
		else if(seg[n+n][a] < seg[n+n+1][b])seg[n].push_back(seg[n+n][a++]);
		else seg[n].push_back(seg[n+n+1][b++]);
	}
}

int get(int l,int r,int L,int R,int n=1,int s = 1,int e = ::T){
	if(s > r || e < l || l > r)return 0;
	if(s >= l && e <= r){
		int fr = lower_bound(all(seg[n]) , L) - seg[n].begin();
		int to = upper_bound(all(seg[n]) , R) - seg[n].begin();
		// cerr << L << ' ' << R << ' ' << to << ' ' << fr << '\n';
		// for(int i : seg[n])
		// 	cerr << i << ' ';
		// cerr << '\n';
		to--;
		// cerr << to-fr+1 << '\n';
		return to - fr + 1;
	}

	return get(l,r,L,R,n+n,s,(s+e)/2) + get(l,r,L,R,n+n+1,(s+e)/2+1,e);
}


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);
	}
	val.resize(n*2+1);
	for(int i=0;i<n;i++){
		// cerr << i << ' ' << fr[0][i] << ' ' << fr[1][i] << '\n';
		val[fr[0][i]] = fr[1][i];
	}
	// return {};
	build();
	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;
		// cerr << i << ' ' << id << ' ' << fr[0][id] << ' ' << to[0][id] << '\n';
		A[e[i].id] = get(fr[0][id] , to[0][id],fr[1][id2],to[1][id2]) > 0;
	}
	// cerr << "WTF\n";


	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:88:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  while(a < seg[n+n].size() || b < seg[n+n+1].size()){
      |        ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:88:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  while(a < seg[n+n].size() || b < seg[n+n+1].size()){
      |                               ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:89:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   if(a == seg[n+n].size())seg[n].push_back(seg[n+n+1][b++]);
      |      ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp:90:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   else if(b == seg[n+n+1].size())seg[n].push_back(seg[n+n][a++]);
      |           ~~^~~~~~~~~~~~~~~~~~~~
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:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:125:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |  for(int i=0;i<S.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:134:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:159:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:185:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |  for(int i=0;i<e.size();i++){
      |              ~^~~~~~~~~

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