oj.uz

Submission #722181

# Submission time Handle Problem Language Result Execution time Memory
722181 2023-04-11T13:52:48 Z minhcool Werewolf (IOI18_werewolf) C++17
100 / 100
 3457 ms 397616 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

set<ii> poss;

// comp1[]: from high to low, this guy is at component from this time to that time
vector<ii> comp1[N], comp2[N];

int n;
vector<int> Adj[N];

int sz[N], rt[N];

vector<int> nodes[N];

int root(int x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

bool ck = 0;

void merge(int x, int y, int ti){
	//cout << "OK " << x << " " << y << " " << ti << "\n";
	x = root(x), y = root(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x, y);
	for(auto it : nodes[y]){
		if(!ck){
			while(comp1[it].size() && comp1[it].back().fi == ti) comp1[it].pop_back();
			comp1[it].pb({ti, x});
		}
		else{
			while(comp2[it].size() && comp2[it].back().fi == ti) comp2[it].pop_back();
			comp2[it].pb({ti, x});
		}
		nodes[x].pb(it);
	}
	nodes[y].clear();
	sz[x] += sz[y];
	rt[y] = x;
}

int cnt;

struct chash{
	int operator()(const ii&a)const{
		return (a.fi * 43920342 + a.se);
	}
};

gp_hash_table<int, int> uomp[N];

vector<ii> vc[N * 10];

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;
	for(int i = 0; i < X.size(); i++){
		Adj[X[i] + 1].pb(Y[i] + 1);
		Adj[Y[i] + 1].pb(X[i] + 1);
	}
	ck = 0;
	for(int i = n; i >= 1; i--){
		//comp1[i].pb({n + 1, -1});
		comp1[i].pb({i, i});
		sz[i] = 1, rt[i] = i;
		nodes[i].pb(i);
		for(auto it : Adj[i]){
			if(it < i) continue;
			merge(i, it, i);
		}
	}
	ck = 1;
	for(int i = 1; i <= n; i++){
		comp1[i].pb({0, 0});
		sz[i] = 0, rt[i] = 0, nodes[i].clear();
	}
	for(int i = 1; i <= n; i++){
		comp2[i].pb({i, i});
		sz[i] = 1, rt[i] = i, nodes[i].pb(i);
		for(auto it : Adj[i]){
			if(it > i) continue;
			merge(i, it, i);
		}
	}
	for(int i = 1; i <= n; i++) comp2[i].pb({n + 1, 0});
	for(int node = 1; node <= n; node++){
		for(int i = 0; (i + 1) < comp1[node].size(); i++){
			for(int j = 0; (j + 1) < comp2[node].size(); j++){
			//	cout << node << " " << comp1[node][i].fi << " " << comp1[node][i].se << " " << comp2[node][j].fi << " " << comp2[node][j].se << "\n";
				if(uomp[comp1[node][i].se].find(comp2[node][j].se) == uomp[comp1[node][i].se].end()){
					cnt++;
					uomp[comp1[node][i].se][comp2[node][j].se] = cnt;
				}
				vc[uomp[comp1[node][i].se][comp2[node][j].se]].pb({comp1[node][i].fi, comp2[node][j].fi});
				//ii seg = {comp1[node][i + 1].fi + 1, comp1[node][i].fi};
				//seg.fi = max(seg.fi, comp2[node][j].fi);
				//seg.se = min(seg.se, comp2[node][j + 1].fi - 1);
				//if(seg.fi > seg.se) continue;
				//upd(1, 1, n, seg.fi, seg.se, {comp1[node][i].se, comp2[node][j].se});
			}
		}
	}
	for(int i = 1; i <= cnt; i++){
		sort(vc[i].begin(), vc[i].end());
		vector<ii> temp;
		for(auto it : vc[i]){
			while(temp.size() && temp.back().se >= it.se) temp.pop_back();
			temp.pb(it);
		}
		vc[i] = temp;
	}
	vector<int> answ(S.size());
	for(int i = 0; i < S.size(); i++){
		S[i]++, E[i]++, L[i]++, R[i]++;
		ii mn = {oo, oo};
		for(auto it : comp1[S[i]]) if(it.fi >= L[i]) mn = min(mn, it);
		ii mx = {-oo, -oo};
		for(auto it : comp2[E[i]]) if(it.fi <= R[i]) mx = max(mx, it);
	//	cout << mn.se << " " << mx.se << " " << L[i] << " " << R[i] << "\n";
		if(uomp[mn.se].find(mx.se) == uomp[mn.se].end()) answ[i] = 0;
		else{
			int temp = uomp[mn.se][mx.se];
			vector<ii>::iterator it = lower_bound(vc[temp].begin(), vc[temp].end(), make_pair(L[i], -oo));
			if(it == vc[temp].end() || (*it).se > R[i]) answ[i] = 0;
			else answ[i] = 1;
		}
	}
	return answ;
}

Compilation message

werewolf.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
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:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i = 0; i < X.size(); i++){
      |                 ~~^~~~~~~~~~
werewolf.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i = 0; (i + 1) < comp1[node].size(); i++){
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for(int j = 0; (j + 1) < comp2[node].size(); j++){
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for(int i = 0; i < S.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162380 KB Output is correct
2 Correct 110 ms 162316 KB Output is correct
3 Correct 104 ms 162236 KB Output is correct
4 Correct 101 ms 162224 KB Output is correct
5 Correct 102 ms 162344 KB Output is correct
6 Correct 100 ms 162372 KB Output is correct
7 Correct 101 ms 162364 KB Output is correct
8 Correct 134 ms 162472 KB Output is correct
9 Correct 100 ms 162252 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162380 KB Output is correct
2 Correct 110 ms 162316 KB Output is correct
3 Correct 104 ms 162236 KB Output is correct
4 Correct 101 ms 162224 KB Output is correct
5 Correct 102 ms 162344 KB Output is correct
6 Correct 100 ms 162372 KB Output is correct
7 Correct 101 ms 162364 KB Output is correct
8 Correct 134 ms 162472 KB Output is correct
9 Correct 100 ms 162252 KB Output is correct
10 Correct 114 ms 163404 KB Output is correct
11 Correct 114 ms 163532 KB Output is correct
12 Correct 120 ms 164376 KB Output is correct
13 Correct 109 ms 163244 KB Output is correct
14 Correct 106 ms 163280 KB Output is correct
15 Correct 114 ms 163452 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3457 ms 378344 KB Output is correct
2 Correct 723 ms 239240 KB Output is correct
3 Correct 868 ms 264660 KB Output is correct
4 Correct 1323 ms 305016 KB Output is correct
5 Correct 1425 ms 313552 KB Output is correct
6 Correct 2114 ms 337036 KB Output is correct
7 Correct 3147 ms 397616 KB Output is correct
8 Correct 630 ms 239020 KB Output is correct
9 Correct 776 ms 264328 KB Output is correct
10 Correct 1170 ms 304844 KB Output is correct
11 Correct 1335 ms 309908 KB Output is correct
12 Correct 2065 ms 338716 KB Output is correct
13 Correct 501 ms 221120 KB Output is correct
14 Correct 524 ms 220216 KB Output is correct
15 Correct 489 ms 220704 KB Output is correct
16 Correct 487 ms 220780 KB Output is correct
17 Correct 3243 ms 391096 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 162380 KB Output is correct
2 Correct 110 ms 162316 KB Output is correct
3 Correct 104 ms 162236 KB Output is correct
4 Correct 101 ms 162224 KB Output is correct
5 Correct 102 ms 162344 KB Output is correct
6 Correct 100 ms 162372 KB Output is correct
7 Correct 101 ms 162364 KB Output is correct
8 Correct 134 ms 162472 KB Output is correct
9 Correct 100 ms 162252 KB Output is correct
10 Correct 114 ms 163404 KB Output is correct
11 Correct 114 ms 163532 KB Output is correct
12 Correct 120 ms 164376 KB Output is correct
13 Correct 109 ms 163244 KB Output is correct
14 Correct 106 ms 163280 KB Output is correct
15 Correct 114 ms 163452 KB Output is correct
16 Correct 3457 ms 378344 KB Output is correct
17 Correct 723 ms 239240 KB Output is correct
18 Correct 868 ms 264660 KB Output is correct
19 Correct 1323 ms 305016 KB Output is correct
20 Correct 1425 ms 313552 KB Output is correct
21 Correct 2114 ms 337036 KB Output is correct
22 Correct 3147 ms 397616 KB Output is correct
23 Correct 630 ms 239020 KB Output is correct
24 Correct 776 ms 264328 KB Output is correct
25 Correct 1170 ms 304844 KB Output is correct
26 Correct 1335 ms 309908 KB Output is correct
27 Correct 2065 ms 338716 KB Output is correct
28 Correct 501 ms 221120 KB Output is correct
29 Correct 524 ms 220216 KB Output is correct
30 Correct 489 ms 220704 KB Output is correct
31 Correct 487 ms 220780 KB Output is correct
32 Correct 3243 ms 391096 KB Output is correct
33 Correct 1706 ms 259492 KB Output is correct
34 Correct 359 ms 193612 KB Output is correct
35 Correct 1378 ms 236188 KB Output is correct
36 Correct 2163 ms 274088 KB Output is correct
37 Correct 1335 ms 238904 KB Output is correct
38 Correct 1982 ms 262752 KB Output is correct
39 Correct 979 ms 230276 KB Output is correct
40 Correct 1049 ms 240768 KB Output is correct
41 Correct 1433 ms 242088 KB Output is correct
42 Correct 1944 ms 273400 KB Output is correct
43 Correct 971 ms 231144 KB Output is correct
44 Correct 1318 ms 239348 KB Output is correct
45 Correct 795 ms 225772 KB Output is correct
46 Correct 907 ms 231008 KB Output is correct
47 Correct 540 ms 220812 KB Output is correct
48 Correct 525 ms 220596 KB Output is correct
49 Correct 575 ms 220604 KB Output is correct
50 Correct 512 ms 220624 KB Output is correct
51 Correct 1029 ms 243220 KB Output is correct
52 Correct 1075 ms 244164 KB Output is correct