oj.uz

Submission #434022

# Submission time Handle Problem Language Result Execution time Memory
434022 2021-06-20T14:08:49 Z frodakcin Werewolf (IOI18_werewolf) C++11
49 / 100
 4000 ms 38836 KB 
#include "werewolf.h"
#include <algorithm>
#include <functional>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

const int MN = 2e5+10;
const int MQ = 2e5+10;

int N, M, Q;
std::vector<int> a[MN], ans;

struct ST
{
	public:
		std::vector<int> v;
		int S;
		ST(int _S): S(_S), v(_S*4, 0) {}

		void build(int n, int l, int r, const std::vector<int>& line)
		{
			if(r-l>1)
			{
				int m = l+(r-l)/2;
				build(n<<1, l, m, line);
				build(n<<1|1, m, r, line);
				v[n]=std::min(v[n<<1], v[n<<1|1]);
			}
			else
				v[n]=line[l];
		}
		void build(const std::vector<int>& line) {build(1, 0, S, line);}

		int qryr(int n, int l, int r, int qr, int cut) //rightmost point < cut
		{
			if(v[n]>=cut) return l-1;
			if(r-l>1)
			{
				int m=l+(r-l)/2, f=m-1;
				if(m < qr) f = qryr(n<<1|1, m, r, qr, cut);
				if(f == m-1) return qryr(n<<1, l, m, qr, cut);
				return f;
			}
			return l;
		}
		int qryr(int qr, int cut) {return qryr(1, 0, S, qr, cut);}

		int qryl(int n, int l, int r, int ql, int cut) //leftmost point < cut
		{
			if(v[n]>=cut) return r;
			if(r-l>1)
			{
				int m=l+(r-l)/2, f=m;
				if(ql < m) f = qryl(n<<1, l, m, ql, cut);
				if(f == m) return qryl(n<<1|1, m, r, ql, cut);
				return f;
			}
			return l;
		}
		int qryl(int ql, int cut) {return qryl(1, 0, S, ql, cut);}
};

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	::N=N;
	M=X.size();
	Q = S.size();

	ans.assign(Q, 0);
	for(int i=0;i<M;++i)
	{
		a[X[i]].push_back(Y[i]);
		a[Y[i]].push_back(X[i]);
	}

	bool is_line = M+1 == N;
	for(int i=0;i<N && is_line;++i)
		is_line &= a[i].size() <= 2;
	if(is_line)
	{
		int st = -1;
		for(int i=0;st == -1;++i)
			if(a[i].size() == 1) st = i;
		std::vector<int> line, wh(N, -1);
		std::vector<char> vis(N, 0);

		line.push_back(st);
		for(int i=1;i<N;++i)
		{
			int n=line.back();
			vis[n]=1;
			for(int x:a[n])
				if(!vis[x])
					line.push_back(x);
		}
		for(int i=0;i<N;++i) wh[line[i]]=i;

		ST hu(N), ww(N);
		hu.build(line);
		for(int& x:line) x*=-1;
		ww.build(line);

		for(int i=0;i<Q;++i)
		{
			int s=wh[S[i]], e=wh[E[i]];
			if(s<e)
				ans[i]=hu.qryl(s, L[i]) > ww.qryr(e, -R[i])+1;
			else
				ans[i]=ww.qryl(e, -R[i]) > hu.qryr(s, L[i])+1;
		}

		return ans;
	}

	for(int i=0;i<Q;++i)
	{
		std::vector<char> vh(N, 0), vw(N, 0);

		std::function<void(int)> dfs=[&](int n)
		{
			vh[n]=1;
			for(int x:a[n])
				if(!vh[x] && x >= L[i])
					dfs(x);
		};
		dfs(S[i]);

		dfs = [&](int n)
		{
			vw[n]=1;
			for(int x:a[n])
				if(!vw[x] && x <= R[i])
					dfs(x);
		};
		dfs(E[i]);

		for(int j=0;!ans[i] && j<N;++j)
		{
			//printf("%d: %d: [%d/%d]\n", i, j, vh[j], vw[j]);
			ans[i] |= vh[j] && vw[j];
		}
	}
  return ans;
}

Compilation message

werewolf.cpp: In constructor 'ST::ST(int)':
werewolf.cpp:18:7: warning: 'ST::S' will be initialized after [-Wreorder]
   18 |   int S;
      |       ^
werewolf.cpp:17:20: warning:   'std::vector<int> ST::v' [-Wreorder]
   17 |   std::vector<int> v;
      |                    ^
werewolf.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   ST(int _S): S(_S), v(_S*4, 0) {}
      |   ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4980 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4980 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 318 ms 5244 KB Output is correct
11 Correct 186 ms 5228 KB Output is correct
12 Correct 7 ms 5304 KB Output is correct
13 Correct 349 ms 5248 KB Output is correct
14 Correct 257 ms 5228 KB Output is correct
15 Correct 299 ms 5508 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 30408 KB Output is correct
2 Correct 380 ms 38712 KB Output is correct
3 Correct 380 ms 38780 KB Output is correct
4 Correct 387 ms 38776 KB Output is correct
5 Correct 387 ms 38716 KB Output is correct
6 Correct 421 ms 38788 KB Output is correct
7 Correct 383 ms 38708 KB Output is correct
8 Correct 345 ms 38832 KB Output is correct
9 Correct 330 ms 38792 KB Output is correct
10 Correct 359 ms 38772 KB Output is correct
11 Correct 355 ms 38836 KB Output is correct
12 Correct 348 ms 38780 KB Output is correct
13 Correct 382 ms 38708 KB Output is correct
14 Correct 362 ms 38708 KB Output is correct
15 Correct 360 ms 38708 KB Output is correct
16 Correct 351 ms 38708 KB Output is correct
17 Correct 411 ms 38832 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4980 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 318 ms 5244 KB Output is correct
11 Correct 186 ms 5228 KB Output is correct
12 Correct 7 ms 5304 KB Output is correct
13 Correct 349 ms 5248 KB Output is correct
14 Correct 257 ms 5228 KB Output is correct
15 Correct 299 ms 5508 KB Output is correct
16 Correct 500 ms 30408 KB Output is correct
17 Correct 380 ms 38712 KB Output is correct
18 Correct 380 ms 38780 KB Output is correct
19 Correct 387 ms 38776 KB Output is correct
20 Correct 387 ms 38716 KB Output is correct
21 Correct 421 ms 38788 KB Output is correct
22 Correct 383 ms 38708 KB Output is correct
23 Correct 345 ms 38832 KB Output is correct
24 Correct 330 ms 38792 KB Output is correct
25 Correct 359 ms 38772 KB Output is correct
26 Correct 355 ms 38836 KB Output is correct
27 Correct 348 ms 38780 KB Output is correct
28 Correct 382 ms 38708 KB Output is correct
29 Correct 362 ms 38708 KB Output is correct
30 Correct 360 ms 38708 KB Output is correct
31 Correct 351 ms 38708 KB Output is correct
32 Correct 411 ms 38832 KB Output is correct
33 Execution timed out 4040 ms 30796 KB Time limit exceeded
34 Halted 0 ms 0 KB -