oj.uz

Submission #624749

# Submission time Handle Problem Language Result Execution time Memory
624749 2022-08-08T16:47:20 Z 1ne Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 15416 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
	vector<int>parent,sz;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int u,int v){
		u = findsets(u);
		v = findsets(v);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		sz[u]+=sz[v];
		parent[v] = u;
		return true;
	}
};
/*
6 6 3
1 5
1 2
1 3
3 4
0 3
2 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
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 q = (int)S.size();
		vector<int>ans(q,0);
		int m = (int)X.size();
		vector<pair<int,int>>edges;
		for (int i = 0;i<m;++i){
			if (X[i] > Y[i])swap(X[i],Y[i]);
			edges.push_back({X[i],Y[i]});
		}
		sort(edges.begin(),edges.end());
		for (int i = 0;i<q;++i){
			DSU human,wolf;
			human.build(N);
			wolf.build(N);
			for (auto x:edges){
				if (x.first >=L[i] && x.second>=L[i]){
					//cout<<"human"<<" "<<x.first<<" "<<x.second<<'\n';
					human.unionset(x.first,x.second);
				}
				if (x.first <=R[i] && x.second<=R[i]){
				//	cout<<"wolf"<<" "<<x.first<<" "<<x.second<<'\n';
					wolf.unionset(x.first,x.second);
				}
			}
			//cout<<'\n';
			if (S[i] < L[i])ans[i] = 0;
			else if (E[i] > R[i])ans[i] = 0;
			else{
				ans[i] = 1;
			}
		}
		return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -