oj.uz

답안 #433976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433976 2021-06-20T13:04:20 Z frodakcin 늑대인간 (IOI18_werewolf) C++11
0 / 100
 4000 ms 47924 KB 
#include "werewolf.h"
#include <algorithm>
#include <functional>

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4041 ms 47924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -