제출 #341974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341974		Marlov	늑대인간 (IOI18_werewolf)	C++14	15 / 100	684 ms	19748 KiB

werewolf

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

#define maxN 3005


vector<int> adj[maxN];
int maxC=0;

bool visitedS[maxN];
bool visitedE[maxN];

void bfsS(int n,int lb){
	queue<int> q;
	q.push(n);
	fill(visitedS,visitedS+maxN,false);
	while(!q.empty()){
		int cn=q.front();
		q.pop();
		if(cn<lb) continue;
		visitedS[cn]=true;
		for(int a:adj[cn])if(!visitedS[a]){
			q.push(a);
		}
	}
}
void bfsE(int n,int ub){
	queue<int> q;
	q.push(n);
	fill(visitedE,visitedE+maxN,false);
	while(!q.empty()){
		int cn=q.front();
		q.pop();
		if(cn>ub) continue;
		visitedE[cn]=true;
		for(int a:adj[cn])if(!visitedE[a]){
			q.push(a);
		}
	}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	int M=X.size();
	int Q=S.size();
	vector<int> result;
	for(int i=0;i<M;i++){
		int u=X[i];
		int v=Y[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
		maxC=max(maxC,(int)max(adj[v].size(),adj[u].size()));
	}
	//if(M==N-1&&maxC<=2){
		
	//}else{
		for(int i=0;i<Q;i++){
			bfsS(S[i],L[i]);
			bfsE(E[i],R[i]);
			bool possible=false;
			for(int j=L[i];j<=R[i];j++){
				if(visitedS[j]&&visitedE[j]) possible=true;
			}
			if(possible) result.push_back(1);
			else result.push_back(0);
		}
	//}

	return result;
}
/*
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	vector<int> ans=check_validity(6,{5,1,1,3,3,5},{1,2,3,4,0,2},{4,4,5},{2,2,4},{1,2,3},{2,2,4});
	for(int a:ans) cout<<a<<" ";
    return 0;
}
*/

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

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