oj.uz

Submission #379327

# Submission time Handle Problem Language Result Execution time Memory
379327 2021-03-18T01:58:06 Z autumn_eel Werewolf (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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory 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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory 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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory 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 -