oj.uz

답안 #77821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77821 2018-09-30T15:00:38 Z Just_Solve_The_Problem 늑대인간 (IOI18_werewolf) C++11
49 / 100
 2099 ms 65084 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

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;
}

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;
	vector < int > ans;

	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 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5328 KB Output is correct
5 Correct 6 ms 5328 KB Output is correct
6 Correct 7 ms 5328 KB Output is correct
7 Correct 7 ms 5328 KB Output is correct
8 Correct 7 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5328 KB Output is correct
5 Correct 6 ms 5328 KB Output is correct
6 Correct 7 ms 5328 KB Output is correct
7 Correct 7 ms 5328 KB Output is correct
8 Correct 7 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 320 ms 5764 KB Output is correct
11 Correct 183 ms 5764 KB Output is correct
12 Correct 36 ms 5764 KB Output is correct
13 Correct 363 ms 5772 KB Output is correct
14 Correct 226 ms 5772 KB Output is correct
15 Correct 272 ms 5808 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2099 ms 65000 KB Output is correct
2 Correct 1141 ms 65024 KB Output is correct
3 Correct 1126 ms 65024 KB Output is correct
4 Correct 1242 ms 65024 KB Output is correct
5 Correct 1505 ms 65024 KB Output is correct
6 Correct 2032 ms 65024 KB Output is correct
7 Correct 1651 ms 65024 KB Output is correct
8 Correct 990 ms 65024 KB Output is correct
9 Correct 644 ms 65024 KB Output is correct
10 Correct 712 ms 65024 KB Output is correct
11 Correct 752 ms 65024 KB Output is correct
12 Correct 608 ms 65024 KB Output is correct
13 Correct 1231 ms 65024 KB Output is correct
14 Correct 1327 ms 65024 KB Output is correct
15 Correct 1296 ms 65080 KB Output is correct
16 Correct 1260 ms 65084 KB Output is correct
17 Correct 1536 ms 65084 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5328 KB Output is correct
5 Correct 6 ms 5328 KB Output is correct
6 Correct 7 ms 5328 KB Output is correct
7 Correct 7 ms 5328 KB Output is correct
8 Correct 7 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 320 ms 5764 KB Output is correct
11 Correct 183 ms 5764 KB Output is correct
12 Correct 36 ms 5764 KB Output is correct
13 Correct 363 ms 5772 KB Output is correct
14 Correct 226 ms 5772 KB Output is correct
15 Correct 272 ms 5808 KB Output is correct
16 Correct 2099 ms 65000 KB Output is correct
17 Correct 1141 ms 65024 KB Output is correct
18 Correct 1126 ms 65024 KB Output is correct
19 Correct 1242 ms 65024 KB Output is correct
20 Correct 1505 ms 65024 KB Output is correct
21 Correct 2032 ms 65024 KB Output is correct
22 Correct 1651 ms 65024 KB Output is correct
23 Correct 990 ms 65024 KB Output is correct
24 Correct 644 ms 65024 KB Output is correct
25 Correct 712 ms 65024 KB Output is correct
26 Correct 752 ms 65024 KB Output is correct
27 Correct 608 ms 65024 KB Output is correct
28 Correct 1231 ms 65024 KB Output is correct
29 Correct 1327 ms 65024 KB Output is correct
30 Correct 1296 ms 65080 KB Output is correct
31 Correct 1260 ms 65084 KB Output is correct
32 Correct 1536 ms 65084 KB Output is correct
33 Incorrect 553 ms 65084 KB Output isn't correct
34 Halted 0 ms 0 KB -