oj.uz

Submission #766084

# Submission time Handle Problem Language Result Execution time Memory
766084 2023-06-25T09:57:01 Z sentheta Werewolf (IOI18_werewolf) C++17
15 / 100
 284 ms 152748 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[3*N];
int tn;
struct Dsu{
	int p[3*N];
	void reset(){
		tn = n;
		rep(x,0,3*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++;

		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);
	rep(x,0,n){
		ordx[x] = tin[x];
		byordx[ordx[x]].push_back(x);
	}
	rep(i,0,q){
		// get segment
		qxl[i] = tin[qroot[i]];
		qxr[i] = tout[qroot[i]];
		byqxl[qxl[i]].push_back(i);
		byqxr[qxr[i]].push_back(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);
	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(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 45012 KB Output is correct
2 Correct 23 ms 45012 KB Output is correct
3 Correct 22 ms 44900 KB Output is correct
4 Correct 22 ms 44944 KB Output is correct
5 Correct 22 ms 44988 KB Output is correct
6 Correct 22 ms 45004 KB Output is correct
7 Correct 22 ms 44928 KB Output is correct
8 Correct 21 ms 44884 KB Output is correct
9 Correct 22 ms 44896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45012 KB Output is correct
2 Correct 23 ms 45012 KB Output is correct
3 Correct 22 ms 44900 KB Output is correct
4 Correct 22 ms 44944 KB Output is correct
5 Correct 22 ms 44988 KB Output is correct
6 Correct 22 ms 45004 KB Output is correct
7 Correct 22 ms 44928 KB Output is correct
8 Correct 21 ms 44884 KB Output is correct
9 Correct 22 ms 44896 KB Output is correct
10 Correct 26 ms 45724 KB Output is correct
11 Correct 28 ms 45688 KB Output is correct
12 Correct 27 ms 45752 KB Output is correct
13 Correct 28 ms 45844 KB Output is correct
14 Correct 29 ms 45808 KB Output is correct
15 Correct 26 ms 45780 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 284 ms 152748 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 45012 KB Output is correct
2 Correct 23 ms 45012 KB Output is correct
3 Correct 22 ms 44900 KB Output is correct
4 Correct 22 ms 44944 KB Output is correct
5 Correct 22 ms 44988 KB Output is correct
6 Correct 22 ms 45004 KB Output is correct
7 Correct 22 ms 44928 KB Output is correct
8 Correct 21 ms 44884 KB Output is correct
9 Correct 22 ms 44896 KB Output is correct
10 Correct 26 ms 45724 KB Output is correct
11 Correct 28 ms 45688 KB Output is correct
12 Correct 27 ms 45752 KB Output is correct
13 Correct 28 ms 45844 KB Output is correct
14 Correct 29 ms 45808 KB Output is correct
15 Correct 26 ms 45780 KB Output is correct
16 Runtime error 284 ms 152748 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -