oj.uz

답안 #77899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77899 2018-10-01T06:24:52 Z Just_Solve_The_Problem 늑대인간 (IOI18_werewolf) C++11
49 / 100
 1727 ms 91472 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
// #include "grader.cpp"

#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define okk puts("OK");

using namespace std;

const int smallN = (int)6e3 + 7;
const int N = (int)2e5 + 7;

int was[smallN];
int used[smallN];
vector < int > gr[N];
int l, r;
int n;
       
void dfs1(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to >= l) dfs1(to, v);
	}
}

void dfs2(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to <= r) dfs2(to, v);
	}
}  

vector < int > subtask12(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	for (int i = 0; i < (int)X.size(); i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	vector < int > ans;
	int q = S.size();
	for (int i = 0; i < q; i++) {
		l = L[i];
		r = R[i];
		memset(was, 0, sizeof was);
		dfs1(S[i], S[i]);
		memset(used, 0, sizeof used);
		dfs2(E[i], E[i]);
		memset(used, 0, sizeof used);
		int ok = 1;
		for (int j = l; j <= r; j++) {
			if (was[j] == 2) {
				ans.pb(1);
				ok = 0;
				break;
			}
		}
		if (ok) {
			ans.pb(0);
		}
	}
	return ans;
}

struct sparse {
	int table[2][20][N];
	/*
	0 = min
	1 = max
 	*/
 	sparse() { 		
 	}
	int numlog[N];
	void build(vector < int > &a) {
		numlog[0] = numlog[1] = 0;
		int nn = a.size();
		for (int i = 2; i < N; i++) {
			numlog[i] = numlog[i / 2] + 1;
		}
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < nn; j++) {
				if (i == 0) {
					table[0][i][j] = table[1][i][j] = a[j];
				} else {
					table[0][i][j] = min(table[0][i - 1][j], table[0][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
					table[1][i][j] = max(table[1][i - 1][j], table[1][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
				}
			}
		}
	}
	int getmax(int l, int r) {
		int lg = numlog[r - l + 1];
		return max(table[1][lg][l], table[1][lg][r - (1 << lg) + 1]);
	}
	int getmin(int l, int r) {
		int lg = numlog[r - l + 1];
		return min(table[0][lg][l], table[0][lg][r - (1 << lg) + 1]);
	}
};

vector < int > ar;
vector < int > pos;
sparse tb;

void dfs3(int v, int pr, int h = 0) {
	ar[h] = v;
	for (int to : gr[v]) {
		if (to != pr) {
			dfs3(to, v, h + 1);
		}
	}
}

pii getrange1(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(max(0, v - md + 1), v) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(v, min(v + md - 1, n - 1)) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}

pii getrange2(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(max(0, v - md + 1), v) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(v, min(v + md - 1, n - 1)) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}

vector < int > subtask3(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();
	ar.resize(n);
	pos.resize(n);
	vector < int > ans;
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	for (int i = 0; i < n; i++) {
		if ((int)gr[i].size() == 1) {
			dfs3(i, i);
			break;
		}
	}         
	tb.build(ar);
	for (int i = 0; i < n; i++) {
		pos[ar[i]] = i;
	}
	int q = (int)S.size();
	ans.resize(q);
	for (int i = 0; i < q; i++) {
		int &res = ans[i];
		res = 0;
		pair < int, int > asd1 = getrange1(pos[S[i]], L[i]);
		pair < int, int > asd2 = getrange2(pos[E[i]], R[i]);
		if ((pos[S[i]] <= pos[E[i]] && asd1.sc >= asd2.fr) || (pos[E[i]] <= pos[S[i]] && asd2.sc >= asd1.fr)) {
			res = 1;
		}
	}  
	return ans;
}

struct DSU {
	int par[N];
	DSU() {
		iota(par, par + N, 0);
	}
	int getpar(int x) {
		return ((par[x] == x) ? x : getpar(par[x]));
	}
};
DSU dsu1, dsu2;

struct query {
	int id, t, x;
	query() {
	}
	query(int _id, int _t, int _x) {
		id = _id;
		t = _t;
		x = _x;
	}
};
vector < query > qq;

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos) {
		while (pos < N) {
			tree[pos]++;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
};
fen tr;

vector < vector < int > > gr1, gr2;
int par[2][20][N];
int tiktak;
int tin[2][N], tout[2][N];
int pos1[N]; 

void dfs(vector < vector < int > > &GR, int id, int v, int pr) {
	par[id][0][v] = pr;
	for (int i = 1; i < 20; i++) {
		par[id][i][v] = par[id][i - 1][par[id][i - 1][v]];
	}
	tin[id][v] = ++tiktak;
	for (int to : GR[v]) {
		dfs(GR, id, to, v);
	}
	tout[id][v] = tiktak;
}

vector < int > subtask4(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();
	int q = S.size();
	vector < int > ans;
	gr1.resize(n);
	gr2.resize(n);
	ans.resize(q);
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}                      
	for (int i = n - 1; i >= 0; i--) {
		for (int to : gr[i]) {
			if (i > to) continue;
			int x = dsu1.getpar(i);
			int y = dsu1.getpar(to);
			if (x == y) continue;
			dsu1.par[y] = x;
			gr1[x].pb(y);
		}
	}                       
	for (int i = 0; i < n; i++) {
		for (int to : gr[i]) {
			if (i < to) continue;
			int x = dsu2.getpar(i);
			int y = dsu2.getpar(to);
			if (x == y) continue;
			dsu2.par[y] = x;
			gr2[x].pb(y);
		}
	}                           
	dfs(gr1, 0, dsu1.getpar(0), dsu1.getpar(0));
	tiktak = 0;
	dfs(gr2, 1, dsu2.getpar(0), dsu2.getpar(0));
	for (int i = 0; i < q; i++) {
		int x = S[i];
		int y = E[i];
		int l = L[i];
		int r = R[i];               
		for (int j = 19; j >= 0; j--) { 
			if (par[0][j][x] >= l) x = par[0][j][x];
			if (par[1][j][y] <= r) y = par[1][j][y];
		}
		cout << i << ' ' << x << ' ' << y << endl;
		qq.pb(query(~i, tin[0][x] - 1, y));
		qq.pb(query(i, tout[0][x], y));
	}
	sort(qq.begin(), qq.end(), [&](query &a, query &b) {
		return a.t < b.t;
	});
	// puts("***");
	for (int i = 0; i < n; i++) {
		pos1[tin[0][i] - 1] = tin[1][i];
	}
	int ord = 0;
	q = (int)qq.size();
	/*for (auto to : qq) {
		cout << to.id << ' ' << to.t << ' ' << to.x << '\n';
	} */
	for (int i = 0; i < q; i++) {
		while (ord < qq[i].t) tr.upd(pos1[ord++]);
		int delta = tr.get(tout[1][qq[i].x]) - tr.get(tin[1][qq[i].x] - 1);
		if (qq[i].id < 0) {
			ans[~qq[i].id] -= delta;
		} else {
			ans[qq[i].id] += delta;
		}
	}
	for (int i = 0; i < n; i++) {
		ans[i] = (ans[i] > 0);
	}
	return ans;                     
}


vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R) {
	if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000) {
		return subtask12(N, X, Y, S, E, L, R);
	} else if ((int)X.size() == N - 1) {
		return subtask3(N, X, Y, S, E, L, R);
	} 
	return subtask4(N, X, Y, S, E, L, R);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 8 ms 7596 KB Output is correct
4 Correct 9 ms 7596 KB Output is correct
5 Correct 9 ms 7596 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 8 ms 7628 KB Output is correct
8 Correct 8 ms 7632 KB Output is correct
9 Correct 8 ms 7764 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 8 ms 7596 KB Output is correct
4 Correct 9 ms 7596 KB Output is correct
5 Correct 9 ms 7596 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 8 ms 7628 KB Output is correct
8 Correct 8 ms 7632 KB Output is correct
9 Correct 8 ms 7764 KB Output is correct
10 Correct 294 ms 8052 KB Output is correct
11 Correct 176 ms 8152 KB Output is correct
12 Correct 31 ms 8416 KB Output is correct
13 Correct 340 ms 8520 KB Output is correct
14 Correct 221 ms 8628 KB Output is correct
15 Correct 272 ms 8900 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1522 ms 67912 KB Output is correct
2 Correct 878 ms 76232 KB Output is correct
3 Correct 790 ms 76444 KB Output is correct
4 Correct 1596 ms 76444 KB Output is correct
5 Correct 1331 ms 76444 KB Output is correct
6 Correct 1727 ms 76444 KB Output is correct
7 Correct 1701 ms 76444 KB Output is correct
8 Correct 817 ms 76444 KB Output is correct
9 Correct 638 ms 76444 KB Output is correct
10 Correct 671 ms 84808 KB Output is correct
11 Correct 791 ms 91280 KB Output is correct
12 Correct 642 ms 91400 KB Output is correct
13 Correct 1104 ms 91400 KB Output is correct
14 Correct 1051 ms 91472 KB Output is correct
15 Correct 1300 ms 91472 KB Output is correct
16 Correct 1098 ms 91472 KB Output is correct
17 Correct 1408 ms 91472 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 8 ms 7596 KB Output is correct
4 Correct 9 ms 7596 KB Output is correct
5 Correct 9 ms 7596 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 8 ms 7628 KB Output is correct
8 Correct 8 ms 7632 KB Output is correct
9 Correct 8 ms 7764 KB Output is correct
10 Correct 294 ms 8052 KB Output is correct
11 Correct 176 ms 8152 KB Output is correct
12 Correct 31 ms 8416 KB Output is correct
13 Correct 340 ms 8520 KB Output is correct
14 Correct 221 ms 8628 KB Output is correct
15 Correct 272 ms 8900 KB Output is correct
16 Correct 1522 ms 67912 KB Output is correct
17 Correct 878 ms 76232 KB Output is correct
18 Correct 790 ms 76444 KB Output is correct
19 Correct 1596 ms 76444 KB Output is correct
20 Correct 1331 ms 76444 KB Output is correct
21 Correct 1727 ms 76444 KB Output is correct
22 Correct 1701 ms 76444 KB Output is correct
23 Correct 817 ms 76444 KB Output is correct
24 Correct 638 ms 76444 KB Output is correct
25 Correct 671 ms 84808 KB Output is correct
26 Correct 791 ms 91280 KB Output is correct
27 Correct 642 ms 91400 KB Output is correct
28 Correct 1104 ms 91400 KB Output is correct
29 Correct 1051 ms 91472 KB Output is correct
30 Correct 1300 ms 91472 KB Output is correct
31 Correct 1098 ms 91472 KB Output is correct
32 Correct 1408 ms 91472 KB Output is correct
33 Incorrect 546 ms 91472 KB Output isn't correct
34 Halted 0 ms 0 KB -