oj.uz

Submission #329346

# Submission time Handle Problem Language Result Execution time Memory
329346 2020-11-20T15:46:41 Z figter001 Werewolf (IOI18_werewolf) C++17
100 / 100
 1640 ms 176964 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 << ' ' << 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

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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37996 KB Output is correct
2 Correct 25 ms 37996 KB Output is correct
3 Correct 25 ms 37868 KB Output is correct
4 Correct 26 ms 37868 KB Output is correct
5 Correct 27 ms 37996 KB Output is correct
6 Correct 26 ms 37996 KB Output is correct
7 Correct 26 ms 37996 KB Output is correct
8 Correct 26 ms 37996 KB Output is correct
9 Correct 26 ms 37996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37996 KB Output is correct
2 Correct 25 ms 37996 KB Output is correct
3 Correct 25 ms 37868 KB Output is correct
4 Correct 26 ms 37868 KB Output is correct
5 Correct 27 ms 37996 KB Output is correct
6 Correct 26 ms 37996 KB Output is correct
7 Correct 26 ms 37996 KB Output is correct
8 Correct 26 ms 37996 KB Output is correct
9 Correct 26 ms 37996 KB Output is correct
10 Correct 36 ms 39660 KB Output is correct
11 Correct 36 ms 39532 KB Output is correct
12 Correct 35 ms 39532 KB Output is correct
13 Correct 42 ms 39788 KB Output is correct
14 Correct 36 ms 39788 KB Output is correct
15 Correct 36 ms 39680 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 152068 KB Output is correct
2 Correct 1383 ms 168416 KB Output is correct
3 Correct 1327 ms 163652 KB Output is correct
4 Correct 1136 ms 161092 KB Output is correct
5 Correct 1167 ms 160900 KB Output is correct
6 Correct 1234 ms 160708 KB Output is correct
7 Correct 1143 ms 160708 KB Output is correct
8 Correct 1346 ms 168516 KB Output is correct
9 Correct 930 ms 163524 KB Output is correct
10 Correct 1034 ms 161220 KB Output is correct
11 Correct 1084 ms 161092 KB Output is correct
12 Correct 959 ms 160836 KB Output is correct
13 Correct 1138 ms 168572 KB Output is correct
14 Correct 1114 ms 168468 KB Output is correct
15 Correct 1151 ms 168532 KB Output is correct
16 Correct 1140 ms 168588 KB Output is correct
17 Correct 1129 ms 160580 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37996 KB Output is correct
2 Correct 25 ms 37996 KB Output is correct
3 Correct 25 ms 37868 KB Output is correct
4 Correct 26 ms 37868 KB Output is correct
5 Correct 27 ms 37996 KB Output is correct
6 Correct 26 ms 37996 KB Output is correct
7 Correct 26 ms 37996 KB Output is correct
8 Correct 26 ms 37996 KB Output is correct
9 Correct 26 ms 37996 KB Output is correct
10 Correct 36 ms 39660 KB Output is correct
11 Correct 36 ms 39532 KB Output is correct
12 Correct 35 ms 39532 KB Output is correct
13 Correct 42 ms 39788 KB Output is correct
14 Correct 36 ms 39788 KB Output is correct
15 Correct 36 ms 39680 KB Output is correct
16 Correct 1217 ms 152068 KB Output is correct
17 Correct 1383 ms 168416 KB Output is correct
18 Correct 1327 ms 163652 KB Output is correct
19 Correct 1136 ms 161092 KB Output is correct
20 Correct 1167 ms 160900 KB Output is correct
21 Correct 1234 ms 160708 KB Output is correct
22 Correct 1143 ms 160708 KB Output is correct
23 Correct 1346 ms 168516 KB Output is correct
24 Correct 930 ms 163524 KB Output is correct
25 Correct 1034 ms 161220 KB Output is correct
26 Correct 1084 ms 161092 KB Output is correct
27 Correct 959 ms 160836 KB Output is correct
28 Correct 1138 ms 168572 KB Output is correct
29 Correct 1114 ms 168468 KB Output is correct
30 Correct 1151 ms 168532 KB Output is correct
31 Correct 1140 ms 168588 KB Output is correct
32 Correct 1129 ms 160580 KB Output is correct
33 Correct 1448 ms 162892 KB Output is correct
34 Correct 420 ms 75756 KB Output is correct
35 Correct 1614 ms 168092 KB Output is correct
36 Correct 1375 ms 161860 KB Output is correct
37 Correct 1562 ms 166880 KB Output is correct
38 Correct 1469 ms 163012 KB Output is correct
39 Correct 1152 ms 176452 KB Output is correct
40 Correct 1286 ms 172352 KB Output is correct
41 Correct 1430 ms 165716 KB Output is correct
42 Correct 1200 ms 161732 KB Output is correct
43 Correct 1640 ms 172608 KB Output is correct
44 Correct 1505 ms 166852 KB Output is correct
45 Correct 1187 ms 176964 KB Output is correct
46 Correct 1383 ms 176724 KB Output is correct
47 Correct 1087 ms 168800 KB Output is correct
48 Correct 1071 ms 168516 KB Output is correct
49 Correct 1157 ms 168644 KB Output is correct
50 Correct 1144 ms 168508 KB Output is correct
51 Correct 1282 ms 173248 KB Output is correct
52 Correct 1254 ms 172992 KB Output is correct