oj.uz

Submission #766100

# Submission time Handle Problem Language Result Execution time Memory
766100 2023-06-25T10:09:24 Z sentheta Werewolf (IOI18_werewolf) C++17
15 / 100
 303 ms 146420 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> byql[N], byqr[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];

// subtree id of the query
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){
		byql[ql[i]].push_back(i);
		byqr[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 : byqr[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]];
	}

	if(n>3000) assert(0);

	// 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 : byql[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 21 ms 39508 KB Output is correct
2 Correct 20 ms 39444 KB Output is correct
3 Correct 20 ms 39472 KB Output is correct
4 Correct 19 ms 39508 KB Output is correct
5 Correct 20 ms 39468 KB Output is correct
6 Correct 22 ms 39508 KB Output is correct
7 Correct 25 ms 39500 KB Output is correct
8 Correct 19 ms 39516 KB Output is correct
9 Correct 21 ms 39444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39508 KB Output is correct
2 Correct 20 ms 39444 KB Output is correct
3 Correct 20 ms 39472 KB Output is correct
4 Correct 19 ms 39508 KB Output is correct
5 Correct 20 ms 39468 KB Output is correct
6 Correct 22 ms 39508 KB Output is correct
7 Correct 25 ms 39500 KB Output is correct
8 Correct 19 ms 39516 KB Output is correct
9 Correct 21 ms 39444 KB Output is correct
10 Correct 24 ms 40204 KB Output is correct
11 Correct 27 ms 40276 KB Output is correct
12 Correct 25 ms 40260 KB Output is correct
13 Correct 26 ms 40252 KB Output is correct
14 Correct 26 ms 40276 KB Output is correct
15 Correct 25 ms 40300 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 303 ms 146420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39508 KB Output is correct
2 Correct 20 ms 39444 KB Output is correct
3 Correct 20 ms 39472 KB Output is correct
4 Correct 19 ms 39508 KB Output is correct
5 Correct 20 ms 39468 KB Output is correct
6 Correct 22 ms 39508 KB Output is correct
7 Correct 25 ms 39500 KB Output is correct
8 Correct 19 ms 39516 KB Output is correct
9 Correct 21 ms 39444 KB Output is correct
10 Correct 24 ms 40204 KB Output is correct
11 Correct 27 ms 40276 KB Output is correct
12 Correct 25 ms 40260 KB Output is correct
13 Correct 26 ms 40252 KB Output is correct
14 Correct 26 ms 40276 KB Output is correct
15 Correct 25 ms 40300 KB Output is correct
16 Runtime error 303 ms 146420 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -