답안 #379327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379327 2021-03-18T01:58:06 Z autumn_eel 늑대인간 (IOI18_werewolf) C++14
15 / 100
4000 ms 16048 KB
#include "werewolf.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

struct UnionFind{
	vector<int>par;
	UnionFind(int n){
		par=vector<int>(n);
		rep(i,n)par[i]=i;
	}
	int find(int x){
		return par[x]==x?x:par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		par[y]=x;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
};

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) {
	int M=X.size();
	int Q=S.size();
	vector<int>ans;
	rep(i,Q){
		UnionFind uf1(N),uf2(N);
		rep(j,M){
			if(X[j]>=L[i]&&Y[j]>=L[i])uf1.unite(X[j],Y[j]);
			if(X[j]<=R[i]&&Y[j]<=R[i])uf2.unite(X[j],Y[j]);
		}
		bool ok=false;
		rep(j,N){
			if(uf1.same(S[i],j)&&uf2.same(E[i],j)){
				ok=true;break;
			}
		}
		ans.push_back(ok);
	}
	return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 496 ms 664 KB Output is correct
11 Correct 426 ms 748 KB Output is correct
12 Correct 370 ms 748 KB Output is correct
13 Correct 468 ms 652 KB Output is correct
14 Correct 370 ms 676 KB Output is correct
15 Correct 1150 ms 748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4046 ms 16048 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 496 ms 664 KB Output is correct
11 Correct 426 ms 748 KB Output is correct
12 Correct 370 ms 748 KB Output is correct
13 Correct 468 ms 652 KB Output is correct
14 Correct 370 ms 676 KB Output is correct
15 Correct 1150 ms 748 KB Output is correct
16 Execution timed out 4046 ms 16048 KB Time limit exceeded
17 Halted 0 ms 0 KB -