oj.uz

Submission #341981

# Submission time Handle Problem Language Result Execution time Memory
341981 2020-12-31T22:07:14 Z Marlov Werewolf (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory 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 -