oj.uz

Submission #344375

# Submission time Handle Problem Language Result Execution time Memory
344375 2021-01-05T15:02:08 Z Marlov Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 21228 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
#define INF 1000000000

vector<int> adj[maxN];
int maxC=0;
int has1child;
vector<int> order;
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);
		}
	}
}

int treemax[4*maxN];
int treemin[4*maxN];
void buildmin(int index,int L,int R){
	if(L==R){
		treemin[index]=order[L];
		return;
	}
	buildmin(2*index,L,(L+R)/2);
	buildmin(2*index+1,(L+R+1)/2,R);
	treemin[index]=min(treemin[2*index],treemin[2*index+1]);
}
void buildmax(int index,int L,int R){
	if(L==R){
		treemax[index]=order[L];
		return;
	}
	buildmax(2*index,L,(L+R)/2);
	buildmax(2*index+1,(L+R+1)/2,R);
	treemax[index]=max(treemax[2*index],treemax[2*index+1]);
}
int querymin(int index,int qL,int qR,int L,int R){
		if(R<qL||qR<L) return INF;
		if(qL<=L&&R<=qR) return treemin[index];
		return min(querymin(2*index,qL,qR,L,(L+R)/2),querymin(2*index+1,qL,qR,(L+R)/2+1,R));
}
int querymax(int index,int qL,int qR,int L,int R){
		if(R<qL||qR<L) return -1;
		if(qL<=L&&R<=qR) return treemax[index];
		return max(querymax(2*index,qL,qR,L,(L+R)/2),querymax(2*index+1,qL,qR,(L+R)/2+1,R));
}

int loc[maxN];
int ci=0;
void dfs(int n,int p){
	order.push_back(n);
	loc[n]=ci;
	ci++;
	for(int a:adj[n]) if(a!=p){
		dfs(a,n);
	}
}

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(adj[u].size()==1) has1child=u;
		if(adj[v].size()==1) has1child=v;
	}
	/*if(M==N-1&&maxC<=2){
		dfs(has1child,has1child);
		buildmin(1,0,N-1);
		buildmax(1,0,N-1);
		for(int i=0;i<Q;i++){
			//to left
			int si=loc[S[i]];
			int ei=loc[E[i]];
			if(si<=ei){
				int sa=si,se=ei;
				while(sa<se){
					int mid=(sa+se+1)/2;
					if(querymax(1,sa,mid,0,N-1)<=R[i]){
						sa=mid;
					}else{
						se=mid-1;
					}
				}
				int ea=si,ee=ei;
				while(ea<ee){
					int mid=(ea+ee)/2;
					if(querymin(1,mid,ee,0,N-1)>=L[i]){
						ee=mid;
					}else{
						ea=mid+1;
					}
				}
				if(ea<=sa) result.push_back(1);
				else if(ei<si) result.push_back(0);
			}else{
				int sa=si,se=ei;
				while(sa<se){
					int mid=(sa+se)/2;
					if(querymax(1,sa,mid,0,N-1)<=R[i]){
						se=mid;
					}else{
						sa=mid+1;
					}
				}
				int ea=si,ee=ei;
				while(ea<ee){
					int mid=(ea+ee+1)/2;
					if(querymin(1,mid,ee,0,N-1)>=L[i]){
						ea=mid;
					}else{
						ee=mid-1;
					}
				}
				if(sa<=ea) result.push_back(1);
				else if(ei<si) result.push_back(0);
			}
		}
	}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 32 ms 5356 KB Output is correct
2 Correct 25 ms 5612 KB Output is correct
3 Correct 25 ms 5484 KB Output is correct
4 Correct 23 ms 5356 KB Output is correct
5 Correct 26 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 28 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 25 ms 5484 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5356 KB Output is correct
2 Correct 25 ms 5612 KB Output is correct
3 Correct 25 ms 5484 KB Output is correct
4 Correct 23 ms 5356 KB Output is correct
5 Correct 26 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 28 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 25 ms 5484 KB Output is correct
10 Correct 1010 ms 5868 KB Output is correct
11 Correct 743 ms 5996 KB Output is correct
12 Correct 593 ms 5868 KB Output is correct
13 Correct 1067 ms 5868 KB Output is correct
14 Correct 768 ms 5940 KB Output is correct
15 Correct 1295 ms 5996 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5356 KB Output is correct
2 Correct 25 ms 5612 KB Output is correct
3 Correct 25 ms 5484 KB Output is correct
4 Correct 23 ms 5356 KB Output is correct
5 Correct 26 ms 5356 KB Output is correct
6 Correct 23 ms 5356 KB Output is correct
7 Correct 28 ms 5484 KB Output is correct
8 Correct 23 ms 5356 KB Output is correct
9 Correct 25 ms 5484 KB Output is correct
10 Correct 1010 ms 5868 KB Output is correct
11 Correct 743 ms 5996 KB Output is correct
12 Correct 593 ms 5868 KB Output is correct
13 Correct 1067 ms 5868 KB Output is correct
14 Correct 768 ms 5940 KB Output is correct
15 Correct 1295 ms 5996 KB Output is correct
16 Execution timed out 4037 ms 21228 KB Time limit exceeded
17 Halted 0 ms 0 KB -