답안 #75111 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75111	2018-09-08T11:36:45 Z	Namnamseo	늑대인간 (IOI18_werewolf)	C++17	100 / 100	2183 ms	169764 KB

werewolf

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)

#define all(v) (v).begin(), (v).end()
#define x first
#define y second

#define pb push_back
#define eb emplace_back
using pp=pair<int,int>;

const int MAX_N = 200001;
const int MAX_V = 400001;

int n;

vector<int> gp[MAX_N];

struct asdf {
	int par[MAX_N];
	int tnode[MAX_N];

	vector<int> te[MAX_V];
	int tp[20][MAX_V];
	int tt[MAX_V];
	int v;

	void init(){
		iota(par+1, par+n+1, 1);
		iota(tnode+1, tnode+n+1, 1);
		v = n;
	}

	int root(int x){ return (x == par[x]) ? x : (par[x] = root(par[x])); }

	void connect(int x, int y, int tm){
		x = root(x); y = root(y);
		if(x == y) return;
		int a = tnode[x], b = tnode[y];
		tp[0][a] = tp[0][b] = ++v;
		tt[v] = tm;
		te[v].pb(a); te[v].pb(b);
		par[x] = y; tnode[y] = v;
	}

	int nt;
	int tin[MAX_V];
	int tout[MAX_V];

	void dfs(int x){
		tin[x] = nt + 1;
		if(x <= n) ++nt;
		for(int y:te[x]) dfs(y);
		tout[x] = nt;
	}

	void inflate(){
		rrep(i, 19) rrep(j, v) tp[i][j] = tp[i-1][tp[i-1][j]];
		dfs(v);
	}

	pp get_range(int v, int tb){
		for(int i=19; 0<=i; --i){
			int a = tp[i][v];
			if(!a) continue;
			if(tt[a] <= tb) v = a;
		}

		return {tin[v], tout[v]};
	}
} sl, sr;

struct seg2d {
	const static int M = 262144;
	vector<int> yv[M*2];

	void addp(int x, int y){
		for(x+=M; x; x>>=1) yv[x].pb(y);
	}

	void prepare(){
		for(auto& v:yv) sort(all(v));
	}

	inline bool exist(vector<int>& v, int d, int u){
		auto it = lower_bound(all(v), d);
		return (it != v.end()) && (*it <= u);
	}

	inline bool exist(int l, int r, int d, int u){
		for(l+=M, r+=M; l<=r; l>>=1, r>>=1){
			if(l%2==1){ if(exist(yv[l++], d, u)) return 1; }
			if(r%2==0){ if(exist(yv[r--], d, u)) return 1; }
		}
		return 0;
	}
} d2;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N;
	int m = X.size();
	rep(i, m){
		int x=X[i]+1, y=Y[i]+1;
		gp[x].pb(y); gp[y].pb(x);
	}

	sl.init();
	sr.init();

	for(int i=n; 1<=i; --i){
		for(int j:gp[i]) if(i<=j){
			sl.connect(i, j, n-i+1);
		}
	}

	rrep(i, n) for(int j:gp[i]) if(j<=i){
		sr.connect(i, j, i);
	}

	sl.inflate(); sr.inflate();
	rrep(i, n) d2.addp(sr.tin[i], sl.tin[i]);
	d2.prepare();

	int q = L.size();
	vector<int> ans(q);
	rep(i, q){
		pp xr = sr.get_range(E[i]+1, R[i]+1);
		pp yr = sl.get_range(S[i]+1, n-L[i]);
		ans[i] = d2.exist(xr.x, xr.y, yr.x, yr.y);
	}

	return ans;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	36472 KB	Output is correct
2	Correct	37 ms	36596 KB	Output is correct
3	Correct	36 ms	36672 KB	Output is correct
4	Correct	36 ms	36748 KB	Output is correct
5	Correct	40 ms	36748 KB	Output is correct
6	Correct	36 ms	36748 KB	Output is correct
7	Correct	34 ms	36748 KB	Output is correct
8	Correct	38 ms	36748 KB	Output is correct
9	Correct	35 ms	36784 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	36472 KB	Output is correct
2	Correct	37 ms	36596 KB	Output is correct
3	Correct	36 ms	36672 KB	Output is correct
4	Correct	36 ms	36748 KB	Output is correct
5	Correct	40 ms	36748 KB	Output is correct
6	Correct	36 ms	36748 KB	Output is correct
7	Correct	34 ms	36748 KB	Output is correct
8	Correct	38 ms	36748 KB	Output is correct
9	Correct	35 ms	36784 KB	Output is correct
10	Correct	49 ms	38748 KB	Output is correct
11	Correct	50 ms	38768 KB	Output is correct
12	Correct	46 ms	38768 KB	Output is correct
13	Correct	47 ms	38796 KB	Output is correct
14	Correct	49 ms	38796 KB	Output is correct
15	Correct	47 ms	38812 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1874 ms	163420 KB	Output is correct
2	Correct	1364 ms	166052 KB	Output is correct
3	Correct	1342 ms	166052 KB	Output is correct
4	Correct	1415 ms	166052 KB	Output is correct
5	Correct	1507 ms	166052 KB	Output is correct
6	Correct	1727 ms	166052 KB	Output is correct
7	Correct	1477 ms	166052 KB	Output is correct
8	Correct	1366 ms	166052 KB	Output is correct
9	Correct	1206 ms	166052 KB	Output is correct
10	Correct	943 ms	166052 KB	Output is correct
11	Correct	974 ms	166052 KB	Output is correct
12	Correct	1263 ms	166052 KB	Output is correct
13	Correct	1513 ms	166152 KB	Output is correct
14	Correct	1515 ms	166152 KB	Output is correct
15	Correct	1586 ms	166152 KB	Output is correct
16	Correct	1511 ms	166192 KB	Output is correct
17	Correct	1400 ms	166192 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	36472 KB	Output is correct
2	Correct	37 ms	36596 KB	Output is correct
3	Correct	36 ms	36672 KB	Output is correct
4	Correct	36 ms	36748 KB	Output is correct
5	Correct	40 ms	36748 KB	Output is correct
6	Correct	36 ms	36748 KB	Output is correct
7	Correct	34 ms	36748 KB	Output is correct
8	Correct	38 ms	36748 KB	Output is correct
9	Correct	35 ms	36784 KB	Output is correct
10	Correct	49 ms	38748 KB	Output is correct
11	Correct	50 ms	38768 KB	Output is correct
12	Correct	46 ms	38768 KB	Output is correct
13	Correct	47 ms	38796 KB	Output is correct
14	Correct	49 ms	38796 KB	Output is correct
15	Correct	47 ms	38812 KB	Output is correct
16	Correct	1874 ms	163420 KB	Output is correct
17	Correct	1364 ms	166052 KB	Output is correct
18	Correct	1342 ms	166052 KB	Output is correct
19	Correct	1415 ms	166052 KB	Output is correct
20	Correct	1507 ms	166052 KB	Output is correct
21	Correct	1727 ms	166052 KB	Output is correct
22	Correct	1477 ms	166052 KB	Output is correct
23	Correct	1366 ms	166052 KB	Output is correct
24	Correct	1206 ms	166052 KB	Output is correct
25	Correct	943 ms	166052 KB	Output is correct
26	Correct	974 ms	166052 KB	Output is correct
27	Correct	1263 ms	166052 KB	Output is correct
28	Correct	1513 ms	166152 KB	Output is correct
29	Correct	1515 ms	166152 KB	Output is correct
30	Correct	1586 ms	166152 KB	Output is correct
31	Correct	1511 ms	166192 KB	Output is correct
32	Correct	1400 ms	166192 KB	Output is correct
33	Correct	1964 ms	166192 KB	Output is correct
34	Correct	428 ms	166192 KB	Output is correct
35	Correct	1945 ms	166192 KB	Output is correct
36	Correct	1932 ms	166192 KB	Output is correct
37	Correct	2183 ms	166192 KB	Output is correct
38	Correct	2102 ms	166192 KB	Output is correct
39	Correct	2029 ms	169044 KB	Output is correct
40	Correct	1547 ms	169252 KB	Output is correct
41	Correct	1559 ms	169252 KB	Output is correct
42	Correct	1186 ms	169252 KB	Output is correct
43	Correct	1650 ms	169252 KB	Output is correct
44	Correct	1765 ms	169252 KB	Output is correct
45	Correct	1241 ms	169252 KB	Output is correct
46	Correct	1273 ms	169252 KB	Output is correct
47	Correct	1591 ms	169252 KB	Output is correct
48	Correct	1624 ms	169252 KB	Output is correct
49	Correct	1547 ms	169252 KB	Output is correct
50	Correct	1581 ms	169252 KB	Output is correct
51	Correct	1379 ms	169644 KB	Output is correct
52	Correct	1491 ms	169764 KB	Output is correct

답안 #75111

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0