oj.uz

답안 #329332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329332 2020-11-20T15:23:20 Z figter001 늑대인간 (IOI18_werewolf) C++17
15 / 100
 2776 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(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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 1 ms 500 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 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 1 ms 500 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 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 47 ms 13932 KB Output is correct
11 Correct 45 ms 13164 KB Output is correct
12 Correct 53 ms 11244 KB Output is correct
13 Correct 44 ms 14828 KB Output is correct
14 Correct 48 ms 15020 KB Output is correct
15 Correct 54 ms 12908 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2776 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 1 ms 500 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 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 47 ms 13932 KB Output is correct
11 Correct 45 ms 13164 KB Output is correct
12 Correct 53 ms 11244 KB Output is correct
13 Correct 44 ms 14828 KB Output is correct
14 Correct 48 ms 15020 KB Output is correct
15 Correct 54 ms 12908 KB Output is correct
16 Runtime error 2776 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -