oj.uz

Submission #766098

# Submission time Handle Problem Language Result Execution time Memory
766098 2023-06-25T10:07:30 Z sentheta Werewolf (IOI18_werewolf) C++17
15 / 100
 203 ms 121208 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];

// 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){
		byl[ql[i]].push_back(i);
		byr[qr[i]].push_back(i);
	}

	if(n>3000) assert(0);

	// 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 19 ms 39408 KB Output is correct
2 Correct 22 ms 39440 KB Output is correct
3 Correct 19 ms 39436 KB Output is correct
4 Correct 21 ms 39516 KB Output is correct
5 Correct 22 ms 39508 KB Output is correct
6 Correct 20 ms 39508 KB Output is correct
7 Correct 25 ms 39472 KB Output is correct
8 Correct 20 ms 39508 KB Output is correct
9 Correct 22 ms 39448 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39408 KB Output is correct
2 Correct 22 ms 39440 KB Output is correct
3 Correct 19 ms 39436 KB Output is correct
4 Correct 21 ms 39516 KB Output is correct
5 Correct 22 ms 39508 KB Output is correct
6 Correct 20 ms 39508 KB Output is correct
7 Correct 25 ms 39472 KB Output is correct
8 Correct 20 ms 39508 KB Output is correct
9 Correct 22 ms 39448 KB Output is correct
10 Correct 23 ms 40328 KB Output is correct
11 Correct 24 ms 40312 KB Output is correct
12 Correct 24 ms 40276 KB Output is correct
13 Correct 23 ms 40280 KB Output is correct
14 Correct 23 ms 40268 KB Output is correct
15 Correct 23 ms 40232 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 121208 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 19 ms 39408 KB Output is correct
2 Correct 22 ms 39440 KB Output is correct
3 Correct 19 ms 39436 KB Output is correct
4 Correct 21 ms 39516 KB Output is correct
5 Correct 22 ms 39508 KB Output is correct
6 Correct 20 ms 39508 KB Output is correct
7 Correct 25 ms 39472 KB Output is correct
8 Correct 20 ms 39508 KB Output is correct
9 Correct 22 ms 39448 KB Output is correct
10 Correct 23 ms 40328 KB Output is correct
11 Correct 24 ms 40312 KB Output is correct
12 Correct 24 ms 40276 KB Output is correct
13 Correct 23 ms 40280 KB Output is correct
14 Correct 23 ms 40268 KB Output is correct
15 Correct 23 ms 40232 KB Output is correct
16 Runtime error 203 ms 121208 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -