Submission #722163

#	Time	Username	Problem	Language	Result	Execution time	Memory
722163		minhcool	Werewolf (IOI18_werewolf)	C++17	0 / 100	4053 ms	290912 KiB

werewolf

#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);
	}
};

map<ii, int> uomp;

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.find({comp1[node][i].se, comp2[node][j].se}) == uomp.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.find({mn.se, mx.se}) == uomp.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(mn.se, -oo));
			if(it == vc[temp].end() || (*it).se > R[i]) answ[i] = 0;
			else answ[i] = 1;
		}
	}
	return answ;
}

Compilation message (stderr)

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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51