제출 #624747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624747		1ne	Werewolf (IOI18_werewolf)	C++14	15 / 100	4046 ms	23912 KiB

werewolf

#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{
				for (int j = L[i];j<=R[i];++j){
					if (human.findsets(j) == human.findsets(S[i]) && wolf.findsets(j) == wolf.findsets(E[i])){
						//cout<<i<<" "<<j<<'\n';
						ans[i] = 1;
						break;
					}
				}
			}
		}
		return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51