oj.uz

Submission #791037

# Submission time Handle Problem Language Result Execution time Memory
791037 2023-07-23T11:07:57 Z aymanrs Werewolf (IOI18_werewolf) C++14
100 / 100
 817 ms 157116 KB 
#include<bits/stdc++.h>
using namespace std;
struct node {
	vector<node*> l;
	int a;
	bool v = false;
};
struct vert{
	vector<vert*> l;
	int t, e, ti;
	set<int>* s;
	vector<int> q, Q;
};
int f(int i, int r[]){
	if(r[i] == i) return i;
	return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
	a = f(a, r);
	b = f(b, r);
	if(a == b) return;
	if(s[a] > s[b]){
		r[b] = a;
		s[a] += s[b];
	} else {
		r[a] = b;
		s[b] += s[a];
	}
}
int t;
vector<vert*> F;
vector<int> L, R;
void dfsH(vert* n, map<int, vert*>& cur){
	cur[n->e] = n;
	n->t = t++;
	for(int i : n->q) F[i] = cur.lower_bound(L[i])->second;
	for(vert* c : n->l) dfsH(c, cur);
	cur.erase(n->e);
	n->e = t;
}
void dfsW(vert* n, map<int, vert*>& cur){
	cur[n->e] = n;
	vert* mc = NULL;
	int mx = -1;
	n->t = t++;
	for(vert* c : n->l){
		dfsW(c, cur);
		if(c->e-c->t > mx) {
			mx = c->e - c->t;
			mc = c;
		}
	}
	if(mx == -1){
		n->s = new set<int> ();
		n->s->insert(n->ti);
	} else {
		n->s = mc->s;
		n->s->insert(n->ti);
		for(vert* c : n->l){
			if(c == mc) continue;
			for(int i : *c->s) n->s->insert(i);
		}
	}
	for(int i : n->q) prev(cur.lower_bound(R[i]+1))->second->Q.push_back(i);
	for(int i : n->Q){
		auto p = n->s->lower_bound(F[i]->t);
		if(p != n->s->end() && *p < F[i]->e) L[i]=1;
		else L[i] = 0;
	}
	cur.erase(n->e);
	n->e = t;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>LT, vector<int> RT){
	t = 0;
	L = LT;
	R = RT;
	F.resize(S.size());
	node g[N];
	vert m[N], M[N];
	int r[N], sz[N], c[N];
	for(int i = 0;i < N;i++) {
		m[i].e = M[i].e = i;
		g[i].a = i;
		r[i] = c[i] = i;
		sz[i] = 1;
	}
	for(int i = 0;i < X.size();i++) {
		g[X[i]].l.push_back(&g[Y[i]]);
		g[Y[i]].l.push_back(&g[X[i]]);
	}
	for(int j = 0;j < N;j++){
		node* d = &g[j];
		d->v = true;
		for(node* x : d->l){
			if(!x->v || f(x->a, r) == f(j, r)) continue;
			M[j].l.push_back(&M[c[f(x->a, r)]]);
			merge(x->a, j, r, sz);
			c[f(j, r)] = j;
		}
	}
	for(int i = 0;i < N;i++) {
		r[i] = c[i] = i;
		sz[i] = 1;
		g[i].v = false;
	}
	for(int j = N-1;j >= 0;j--){
		node* d = &g[j];
		d->v = true;
		for(node* x : d->l){
			if(!x->v || f(x->a, r) == f(j, r)) continue;
			m[j].l.push_back(&m[c[f(x->a, r)]]);
			merge(x->a, j, r, sz);
			c[f(j, r)] = j;
		}
	}
	for(int i = 0;i < S.size();i++){
		m[S[i]].q.push_back(i);
		M[E[i]].q.push_back(i);
	}
	map<int, vert*> cur;
	dfsH(&m[0], cur);
	for(int i = 0;i < N;i++) M[i].ti = m[i].t;
	dfsW(&M[N-1], cur);
	return L;
}

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:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0;i < X.size();i++) {
      |                ~~^~~~~~~~~~
werewolf.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i = 0;i < S.size();i++){
      |                ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6 ms 2004 KB Output is correct
11 Correct 5 ms 2004 KB Output is correct
12 Correct 5 ms 2132 KB Output is correct
13 Correct 5 ms 2260 KB Output is correct
14 Correct 5 ms 2260 KB Output is correct
15 Correct 6 ms 2132 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 148172 KB Output is correct
2 Correct 659 ms 124908 KB Output is correct
3 Correct 593 ms 121976 KB Output is correct
4 Correct 579 ms 127052 KB Output is correct
5 Correct 593 ms 128460 KB Output is correct
6 Correct 600 ms 135168 KB Output is correct
7 Correct 662 ms 157116 KB Output is correct
8 Correct 503 ms 119372 KB Output is correct
9 Correct 412 ms 116096 KB Output is correct
10 Correct 440 ms 121220 KB Output is correct
11 Correct 419 ms 122060 KB Output is correct
12 Correct 437 ms 128604 KB Output is correct
13 Correct 721 ms 127708 KB Output is correct
14 Correct 729 ms 127580 KB Output is correct
15 Correct 721 ms 127564 KB Output is correct
16 Correct 710 ms 127756 KB Output is correct
17 Correct 663 ms 156268 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6 ms 2004 KB Output is correct
11 Correct 5 ms 2004 KB Output is correct
12 Correct 5 ms 2132 KB Output is correct
13 Correct 5 ms 2260 KB Output is correct
14 Correct 5 ms 2260 KB Output is correct
15 Correct 6 ms 2132 KB Output is correct
16 Correct 666 ms 148172 KB Output is correct
17 Correct 659 ms 124908 KB Output is correct
18 Correct 593 ms 121976 KB Output is correct
19 Correct 579 ms 127052 KB Output is correct
20 Correct 593 ms 128460 KB Output is correct
21 Correct 600 ms 135168 KB Output is correct
22 Correct 662 ms 157116 KB Output is correct
23 Correct 503 ms 119372 KB Output is correct
24 Correct 412 ms 116096 KB Output is correct
25 Correct 440 ms 121220 KB Output is correct
26 Correct 419 ms 122060 KB Output is correct
27 Correct 437 ms 128604 KB Output is correct
28 Correct 721 ms 127708 KB Output is correct
29 Correct 729 ms 127580 KB Output is correct
30 Correct 721 ms 127564 KB Output is correct
31 Correct 710 ms 127756 KB Output is correct
32 Correct 663 ms 156268 KB Output is correct
33 Correct 689 ms 128900 KB Output is correct
34 Correct 206 ms 44560 KB Output is correct
35 Correct 778 ms 128904 KB Output is correct
36 Correct 668 ms 130892 KB Output is correct
37 Correct 740 ms 127808 KB Output is correct
38 Correct 724 ms 128840 KB Output is correct
39 Correct 817 ms 138376 KB Output is correct
40 Correct 716 ms 135884 KB Output is correct
41 Correct 521 ms 120236 KB Output is correct
42 Correct 467 ms 122424 KB Output is correct
43 Correct 713 ms 128940 KB Output is correct
44 Correct 576 ms 120924 KB Output is correct
45 Correct 584 ms 134828 KB Output is correct
46 Correct 586 ms 134480 KB Output is correct
47 Correct 704 ms 128000 KB Output is correct
48 Correct 752 ms 127632 KB Output is correct
49 Correct 698 ms 127920 KB Output is correct
50 Correct 695 ms 127812 KB Output is correct
51 Correct 665 ms 135248 KB Output is correct
52 Correct 666 ms 135308 KB Output is correct