oj.uz

Submission #77819

# Submission time Handle Problem Language Result Execution time Memory
77819 2018-09-30T14:58:24 Z Just_Solve_The_Problem Werewolf (IOI18_werewolf) C++11
41 / 100
 4000 ms 130848 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)3e6 + 7;
const int N = (int)2e5 + 7;

int was[smallN];
int used[smallN];
vector < int > gr[smallN];
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

# Verdict Execution time Memory Grader output
1 Correct 328 ms 94328 KB Output is correct
2 Correct 318 ms 94460 KB Output is correct
3 Correct 361 ms 94472 KB Output is correct
4 Correct 331 ms 94616 KB Output is correct
5 Correct 321 ms 94616 KB Output is correct
6 Correct 332 ms 94616 KB Output is correct
7 Correct 314 ms 94616 KB Output is correct
8 Correct 301 ms 94616 KB Output is correct
9 Correct 321 ms 94616 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 94328 KB Output is correct
2 Correct 318 ms 94460 KB Output is correct
3 Correct 361 ms 94472 KB Output is correct
4 Correct 331 ms 94616 KB Output is correct
5 Correct 321 ms 94616 KB Output is correct
6 Correct 332 ms 94616 KB Output is correct
7 Correct 314 ms 94616 KB Output is correct
8 Correct 301 ms 94616 KB Output is correct
9 Correct 321 ms 94616 KB Output is correct
10 Execution timed out 4099 ms 94896 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2143 ms 130612 KB Output is correct
2 Correct 1036 ms 130708 KB Output is correct
3 Correct 951 ms 130812 KB Output is correct
4 Correct 1255 ms 130812 KB Output is correct
5 Correct 1229 ms 130812 KB Output is correct
6 Correct 1806 ms 130812 KB Output is correct
7 Correct 1470 ms 130812 KB Output is correct
8 Correct 821 ms 130832 KB Output is correct
9 Correct 640 ms 130832 KB Output is correct
10 Correct 693 ms 130832 KB Output is correct
11 Correct 782 ms 130832 KB Output is correct
12 Correct 670 ms 130832 KB Output is correct
13 Correct 954 ms 130848 KB Output is correct
14 Correct 915 ms 130848 KB Output is correct
15 Correct 992 ms 130848 KB Output is correct
16 Correct 932 ms 130848 KB Output is correct
17 Correct 1355 ms 130848 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 94328 KB Output is correct
2 Correct 318 ms 94460 KB Output is correct
3 Correct 361 ms 94472 KB Output is correct
4 Correct 331 ms 94616 KB Output is correct
5 Correct 321 ms 94616 KB Output is correct
6 Correct 332 ms 94616 KB Output is correct
7 Correct 314 ms 94616 KB Output is correct
8 Correct 301 ms 94616 KB Output is correct
9 Correct 321 ms 94616 KB Output is correct
10 Execution timed out 4099 ms 94896 KB Time limit exceeded
11 Halted 0 ms 0 KB -