oj.uz

답안 #766108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766108 2023-06-25T10:20:54 Z sentheta 늑대인간 (IOI18_werewolf) C++17
15 / 100
 500 ms 79180 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
int inordx[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 && tn==2*n-1);
	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 : byql[x]){
			qroot[i] = dsu.find(qs[i]);
		}
	}
	// euler tour
	tim = 0;
	tdfs(tn);
	assert(tim==n && tn==2*n-1);
	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){
		assert(0<=ordx[x] && ordx[x]<n);
		inordx[ordx[x]] = x;
		// byordx[0].push_back(0);
	}
	// assert(0);
	rep(i,0,q){
		byqxl[qxl[i]].push_back(i);
		byqxr[qxr[i]].push_back(i);
	}
	rep(t,0,n){
		// insert points
		int node = inordx[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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 16 ms 34812 KB Output is correct
3 Correct 17 ms 34816 KB Output is correct
4 Correct 16 ms 34756 KB Output is correct
5 Correct 17 ms 34828 KB Output is correct
6 Correct 17 ms 34760 KB Output is correct
7 Correct 17 ms 34828 KB Output is correct
8 Correct 18 ms 34784 KB Output is correct
9 Correct 16 ms 34772 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 16 ms 34812 KB Output is correct
3 Correct 17 ms 34816 KB Output is correct
4 Correct 16 ms 34756 KB Output is correct
5 Correct 17 ms 34828 KB Output is correct
6 Correct 17 ms 34760 KB Output is correct
7 Correct 17 ms 34828 KB Output is correct
8 Correct 18 ms 34784 KB Output is correct
9 Correct 16 ms 34772 KB Output is correct
10 Correct 20 ms 35540 KB Output is correct
11 Correct 20 ms 35540 KB Output is correct
12 Correct 20 ms 35400 KB Output is correct
13 Correct 22 ms 35504 KB Output is correct
14 Correct 26 ms 35648 KB Output is correct
15 Correct 21 ms 35540 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 500 ms 79180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 34772 KB Output is correct
2 Correct 16 ms 34812 KB Output is correct
3 Correct 17 ms 34816 KB Output is correct
4 Correct 16 ms 34756 KB Output is correct
5 Correct 17 ms 34828 KB Output is correct
6 Correct 17 ms 34760 KB Output is correct
7 Correct 17 ms 34828 KB Output is correct
8 Correct 18 ms 34784 KB Output is correct
9 Correct 16 ms 34772 KB Output is correct
10 Correct 20 ms 35540 KB Output is correct
11 Correct 20 ms 35540 KB Output is correct
12 Correct 20 ms 35400 KB Output is correct
13 Correct 22 ms 35504 KB Output is correct
14 Correct 26 ms 35648 KB Output is correct
15 Correct 21 ms 35540 KB Output is correct
16 Incorrect 500 ms 79180 KB Output isn't correct
17 Halted 0 ms 0 KB -