Submission #413635

#	Time	Username	Problem	Language	Result	Execution time	Memory
413635		LastRonin	Werewolf (IOI18_werewolf)	C++14	100 / 100	1898 ms	262348 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define ll long long
#define pb push_back
using namespace std;

const ll N = 3e5;


int n;
vector<int> g[N];
vector<int> nt[2][N];

struct DSU {
	ll p[N] = {0};
	ll get(ll v) {     
		return p[v] = (p[v] == v ? v : get(p[v]));
	}
} rot[2];

ll tin[2][N], tout[2][N];
ll bp[2][N][20];
int arr[2][N];

void dfs(ll v, ll p, ll t) {
	bp[t][v][0] = p;
	tin[t][v] = ++tout[t][0];
	arr[t][tin[t][v]] = v;
	for(int j = 1; j < 20; j++)
		bp[t][v][j] = bp[t][bp[t][v][j - 1]][j - 1];
	for(auto u : nt[t][v]) {
		dfs(u, v, t);	
	}		
	tout[t][v] = tout[t][0];
}

struct node {
	node *l = nullptr, *r = nullptr;
	ll sum = 0;
	node() {};
} *rt[N];

void bld(node *v, ll l = 1, ll r = n) {
	if(l == r) 
		return;
	ll m = (l + r) >> 1ll;	
	v->l = new node();
	v->r = new node();
	bld(v->l, l, m);
	bld(v->r, m + 1, r);	
}

void upd(ll p, node *v, node *u, ll l = 1, ll r = n) {
	if(l == r) {
		v->sum = 1;
		return;
	}
	ll m = (l + r) >> 1ll;
	if(p <= m) {
		v->r = u->r;
		v->l = new node();
		upd(p, v->l, u->l, l, m);
	}
	else {
		v->l = u->l;
		v->r = new node();
		upd(p, v->r, u->r, m + 1, r);
	}
	v->sum = v->l->sum + v->r->sum;
}

ll get(ll l, ll r, node *v, ll tl = 1, ll tr = n) {
	if(l > tr || tl > r)
		return 0;
	if(l <= tl && tr <= r)
		return (v->sum);
	ll m = (tl + tr) >> 1ll;
	return get(l, r, v->l, tl, m) + get(l, r, v->r, m + 1, tr);
}

vector<int> check_validity(int NN, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
	n = NN;
	for(int i = 0; i < x.size(); i++) {
		x[i]++, y[i]++;
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);		
	}
	for(int i = n; i >= 1; i--) {
		rot[0].p[i] = i;
		for(auto u : g[i]) {
			if(u < i)continue;
			ll z = rot[0].get(u);
			if(z == i)continue;
			nt[0][i].pb(z);
			rot[0].p[z] = i;			 
		}
	}   
	for(int i = 1; i <= n; i++) {
		rot[1].p[i] = i;
		for(auto u : g[i]) {
			if(u > i)continue;			
			ll z = rot[1].get(u);
			if(z == i)continue;
			nt[1][i].pb(z);
			rot[1].p[z] = i;
		}
	}
	dfs(1, 0, 0), dfs(n, 0, 1);
	rt[0] = new node();
	bld(rt[0]);
	for(int i = 1; i <= n; i++) {
		rt[i] = new node();
		upd(tin[1][arr[0][i]], rt[i], rt[i - 1]);							
	}
	vector<int> sub;
	for(int i = 0; i < s.size(); i++) {
		ll vs = s[i] + 1, ve = e[i] + 1;
		ll L = l[i] + 1, R = r[i] + 1;
		for(int j = 19; j >= 0; j--) {
			if(bp[0][vs][j] >= L) 
				vs = bp[0][vs][j];
		}
		for(int j = 19; j >= 0; j--) {
			if(bp[1][ve][j] && bp[1][ve][j] <= R)
				ve = bp[1][ve][j]; 
		}
		ll l1 = tin[0][vs], r1 = tout[0][vs];
		ll l2 = tin[1][ve], r2 = tout[1][ve];
		ll h = get(l2, r2, rt[r1]) - get(l2, r2, rt[l1 - 1]);
		sub.pb((h?1:0));
	}
	return sub;                                                	
}

/*
int main() {
	int p, m, q;
	cin >> p >> m >> q;
	vector<int> x,y,l,r,s,e;
	for(int i = 1; i <= m; i++) {
		ll a, b;
		cin >> a >> b;
		x.pb(a),y.pb(b);
	}
	while(q--) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		l.pb(c), r.pb(d);
		s.pb(a), e.pb(b);
	}
	vector<int> ans = check_validaty(p, x, y, s, e, l, r);
	for(auto u : ans)
		cout << u << " ";
	
} */  

Compilation message (stderr)

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:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
werewolf.cpp:116:19: 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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51