oj.uz

답안 #341981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341981 2020-12-31T22:07:14 Z Marlov 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 21852 KB 
/*
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 200005


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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5484 KB Output is correct
2 Correct 25 ms 5484 KB Output is correct
3 Correct 25 ms 5356 KB Output is correct
4 Correct 23 ms 5484 KB Output is correct
5 Correct 23 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 23 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 23 ms 5356 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5484 KB Output is correct
2 Correct 25 ms 5484 KB Output is correct
3 Correct 25 ms 5356 KB Output is correct
4 Correct 23 ms 5484 KB Output is correct
5 Correct 23 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 23 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 23 ms 5356 KB Output is correct
10 Correct 1004 ms 5996 KB Output is correct
11 Correct 727 ms 5740 KB Output is correct
12 Correct 595 ms 5740 KB Output is correct
13 Correct 1034 ms 5740 KB Output is correct
14 Correct 769 ms 5740 KB Output is correct
15 Correct 1277 ms 6044 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 21852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5484 KB Output is correct
2 Correct 25 ms 5484 KB Output is correct
3 Correct 25 ms 5356 KB Output is correct
4 Correct 23 ms 5484 KB Output is correct
5 Correct 23 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 23 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 23 ms 5356 KB Output is correct
10 Correct 1004 ms 5996 KB Output is correct
11 Correct 727 ms 5740 KB Output is correct
12 Correct 595 ms 5740 KB Output is correct
13 Correct 1034 ms 5740 KB Output is correct
14 Correct 769 ms 5740 KB Output is correct
15 Correct 1277 ms 6044 KB Output is correct
16 Execution timed out 4062 ms 21852 KB Time limit exceeded
17 Halted 0 ms 0 KB -