oj.uz

Submission #433977

# Submission time Handle Problem Language Result Execution time Memory
433977 2021-06-20T13:05:49 Z frodakcin Werewolf (IOI18_werewolf) C++11
15 / 100
 4000 ms 39652 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;

struct DSU
{
	int S;
	std::vector<int> p, r;
	DSU(int _S): S(_S), p(_S, -1), r(_S, 0) {}
	int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
	bool merge(int a, int b)
	{
		a=find(a), b=find(b);
		if(a==b) return 0;
		if(r[a]<r[b]) std::swap(a,b);
		p[b]=a, r[a]+=r[a]==r[b], r[b]=-1;
		return 1;
	}
};

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

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)
	{
		a0[X[i]].push_back(Y[i]);
		a0[Y[i]].push_back(X[i]);
	}
	DSU dsu(N);
	for(int i=0;i<N;++i)
	{
		std::sort(a0[i].begin(), a0[i].end(), std::greater<int>());
		for(int x:a0[i])
			if(x<i && dsu.merge(x, i))
				a[x].push_back(i), a[i].push_back(x);
	}

	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:a0[n])
				if(!vh[x] && x >= L[i])
					dfs(x);
		};
		dfs(S[i]);

		dfs = [&](int n)
		{
			vw[n]=1;
			for(int x:a0[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;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 8 ms 9676 KB Output is correct
3 Correct 8 ms 9680 KB Output is correct
4 Correct 8 ms 9592 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 8 ms 9676 KB Output is correct
7 Correct 8 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 359 ms 10176 KB Output is correct
11 Correct 198 ms 10128 KB Output is correct
12 Correct 55 ms 10296 KB Output is correct
13 Correct 354 ms 10200 KB Output is correct
14 Correct 233 ms 10052 KB Output is correct
15 Correct 320 ms 10324 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 39652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 8 ms 9676 KB Output is correct
3 Correct 8 ms 9680 KB Output is correct
4 Correct 8 ms 9592 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 8 ms 9676 KB Output is correct
7 Correct 8 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 359 ms 10176 KB Output is correct
11 Correct 198 ms 10128 KB Output is correct
12 Correct 55 ms 10296 KB Output is correct
13 Correct 354 ms 10200 KB Output is correct
14 Correct 233 ms 10052 KB Output is correct
15 Correct 320 ms 10324 KB Output is correct
16 Execution timed out 4054 ms 39652 KB Time limit exceeded
17 Halted 0 ms 0 KB -