oj.uz

Submission #329327

# Submission time Handle Problem Language Result Execution time Memory
329327 2020-11-20T15:19:18 Z figter001 Werewolf (IOI18_werewolf) C++17
15 / 100
 2864 ms 524292 KB 
#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(n == NULL)n = new node2d();
	if(s > at || e < at)return;
	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);
	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

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:183:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:188:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |  for(int i=0;i<S.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:197:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:222:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |   for(int i=0;i<e.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:247:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |  for(int i=0;i<e.size();i++){
      |              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 44 ms 13036 KB Output is correct
11 Correct 42 ms 12140 KB Output is correct
12 Correct 36 ms 10348 KB Output is correct
13 Correct 40 ms 13676 KB Output is correct
14 Correct 39 ms 13932 KB Output is correct
15 Correct 41 ms 11884 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 2864 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 44 ms 13036 KB Output is correct
11 Correct 42 ms 12140 KB Output is correct
12 Correct 36 ms 10348 KB Output is correct
13 Correct 40 ms 13676 KB Output is correct
14 Correct 39 ms 13932 KB Output is correct
15 Correct 41 ms 11884 KB Output is correct
16 Runtime error 2864 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -