제출 #1256426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256426		SmuggingSpun	늑대인간 (IOI18_werewolf)	C++20	15 / 100	741 ms	21544 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
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(), q = S.size();
	vector<vector<int>>g(n);
	for(int i = 0; i < m; i++){
		g[X[i]].emplace_back(i);
		g[Y[i]].emplace_back(i);
	}
	vector<int>ans(q);
	if(n <= 3000 && m <= 6000 && q <= 3000){
		for(int i = 0; i < q; i++){
			vector<vector<bool>>f(n, vector<bool>(2, false));
			queue<pair<int, int>>q;
			q.emplace(S[i], 0);
			f[S[i]][0] = true;
			while(!q.empty()){
				auto [s, c] = q.front();
				q.pop();
				if(c == 0 && L[i] <= s && R[i] >= s){
					f[s][1] = true;
					q.emplace(s, 1);
				}
				for(int& j : g[s]){
					int d = s ^ X[j] ^ Y[j];
					if(((c == 0 & d >= L[i]) || (c == 1 && d <= R[i])) && !f[d][c]){
						f[d][c] = true;
						q.emplace(d, c);
					}
				}
			}
			ans[i] = f[E[i]][1];
		}
	}
	return ans;
}

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