oj.uz

Submission #766094

# Submission time Handle Problem Language Result Execution time Memory
766094 2023-06-25T10:02:36 Z sentheta Werewolf (IOI18_werewolf) C++17
15 / 100
 354 ms 153188 KB 
#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 2e5+5;

int n, m, q;
V<int> adj[N];

V<int> ans;

// queries details
V<int> qs, qt, ql, qr;
// groups of queries with same l values
V<int> byl[N], byr[N];

// segments of queries in tree
int qxl[N], qxr[N];
int qyl[N], qyr[N];
// group queries by x-boundaries
V<int> byqxl[N], byqxr[N];

int qroot[N];

// dsu tree
V<int> tadj[2*N];
int tn;
struct Dsu{
	int p[2*N];
	void reset(){
		tn = n;
		rep(x,0,2*N){
			p[x] = x;
			tadj[x].clear();
		}
	}
	int find(int x){
		if(p[x]==x) return x;
		return p[x] = find(p[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		if((x=find(x))==(y=find(y))) return;
		tn++;
		assert(tn<2*N);

		p[x] = p[y] = tn;
		tadj[tn].push_back(x);
		tadj[tn].push_back(y);
	}
} dsu;

// x-order and y-order of nodes
int ordx[N], ordy[N];
// group nodes by ordx[] values
V<int> byordx[N];

// euler tour
int tin[N], tout[N], tim;
void tdfs(int x){
	tin[x] = tim;
	if(x<n) tim++;
	for(int y : tadj[x]){
		tdfs(y);
	}
	tout[x] = tim-1;
}

// segtree
// point assign update
// range sum query
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
struct Segtree{
	int sum[2*N];
	void upd(int i,int x,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			sum[v] = x; return;
		}
		if(i<=mid) upd(i,x, lc,tl,mid);
		else upd(i,x, rc,mid+1,tr);
		sum[v] = sum[lc] + sum[rc];
	}
	int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 0;
		if(l<=tl && tr<=r) return sum[v];
		return qry(l,r, lc,tl,mid) + qry(l,r, rc,mid+1,tr);
	}
} segtree;



V<int> check_validity(int _n,V<int>_u,V<int>_v,
							V<int>_s,V<int>_t,V<int>_l,V<int>_r){
	n=_n; m=_u.size(); q=_s.size();
	qs.swap(_s); qt.swap(_t); ql.swap(_l); qr.swap(_r);

	rep(i,0,m){
		adj[_u[i]].push_back(_v[i]);
		adj[_v[i]].push_back(_u[i]);
	}

	rep(i,0,q){
		byl[ql[i]].push_back(i);
		byr[qr[i]].push_back(i);
	}

	// bounded right
	dsu.reset();
	rep(x,0,n){
		// make edges with this node
		for(int y : adj[x]) if(y<x){
			dsu.unite(x,y);
		}
		// proccess queries
		for(int i : byr[x]){
			qroot[i] = dsu.find(qt[i]);
		}
	}
	// euler tour
	tim = 0;
	tdfs(tn);
	assert(tim==n);
	rep(x,0,n){
		ordx[x] = tin[x];
	}
	rep(i,0,q){
		// get segment
		qxl[i] = tin[qroot[i]];
		qxr[i] = tout[qroot[i]];
	}

	// bounded left
	dsu.reset();
	for(int x=n-1; x>=0; x--){
		// make edges with this node
		for(int y : adj[x]) if(x<y){
			dsu.unite(x,y);
		}
		// proccess queries
		for(int i : byl[x]){
			qroot[i] = dsu.find(qs[i]);
		}
	}
	// euler tour
	tim = 0;
	tdfs(tn);
	assert(tim==n);
	rep(x,0,n) ordy[x] = tin[x];
	rep(i,0,q){
		// get segment
		qyl[i] = tin[qroot[i]];
		qyr[i] = tout[qroot[i]];
	}

	
	// sweep check for intersecting segment
	ans = V<int>(q);
	rep(x,0,n){
		byordx[ordx[x]].push_back(x);
	}
	rep(i,0,q){
		byqxl[qxl[i]].push_back(i);
		byqxr[qxr[i]].push_back(i);
	}
	rep(t,0,n){
		// insert points
		for(int node : byordx[t]){
			segtree.upd(ordy[node], 1);
		}

		// process queries
		// starting query
		for(int i : byqxl[t+1]){
			ans[i] -= segtree.qry(qyl[i], qyr[i]);
		}
		// ending query
		for(int i : byqxr[t]){
			ans[i] += segtree.qry(qyl[i], qyr[i]);
		}
	}

	// convert to boolean
	rep(i,0,q) ans[i] = ans[i] > 0;
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39508 KB Output is correct
2 Correct 23 ms 39452 KB Output is correct
3 Correct 24 ms 39412 KB Output is correct
4 Correct 22 ms 39448 KB Output is correct
5 Correct 23 ms 39460 KB Output is correct
6 Correct 23 ms 39488 KB Output is correct
7 Correct 26 ms 39508 KB Output is correct
8 Correct 23 ms 39508 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39508 KB Output is correct
2 Correct 23 ms 39452 KB Output is correct
3 Correct 24 ms 39412 KB Output is correct
4 Correct 22 ms 39448 KB Output is correct
5 Correct 23 ms 39460 KB Output is correct
6 Correct 23 ms 39488 KB Output is correct
7 Correct 26 ms 39508 KB Output is correct
8 Correct 23 ms 39508 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct
10 Correct 27 ms 40420 KB Output is correct
11 Correct 26 ms 40404 KB Output is correct
12 Correct 28 ms 40340 KB Output is correct
13 Correct 26 ms 40404 KB Output is correct
14 Correct 27 ms 40456 KB Output is correct
15 Correct 30 ms 40428 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 354 ms 153188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39508 KB Output is correct
2 Correct 23 ms 39452 KB Output is correct
3 Correct 24 ms 39412 KB Output is correct
4 Correct 22 ms 39448 KB Output is correct
5 Correct 23 ms 39460 KB Output is correct
6 Correct 23 ms 39488 KB Output is correct
7 Correct 26 ms 39508 KB Output is correct
8 Correct 23 ms 39508 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct
10 Correct 27 ms 40420 KB Output is correct
11 Correct 26 ms 40404 KB Output is correct
12 Correct 28 ms 40340 KB Output is correct
13 Correct 26 ms 40404 KB Output is correct
14 Correct 27 ms 40456 KB Output is correct
15 Correct 30 ms 40428 KB Output is correct
16 Runtime error 354 ms 153188 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -