oj.uz

Submission #598963

# Submission time Handle Problem Language Result Execution time Memory
598963 2022-07-19T08:25:54 Z fuad27 Werewolf (IOI18_werewolf) C++17
15 / 100
 768 ms 36680 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool same_set(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return true;
	}
};
const int NN = 200'010;
vector<int> topo;
vector<int> g[NN];
vector<bool> vis(NN);
int n;
void dfs(int at) {
	vis[at]=1;
	for(int to:g[at]) {
		if(vis[to])continue;
		dfs(to);
	}
	topo.push_back(at);
}
int Tmx[4*NN],Tmn[4*NN];
void build(int v, int tl, int tr, vector<int> &a) {
	if(tl == tr) {
		Tmx[v]=a[tl];
		Tmn[v]=a[tl];
		return;
	}
	int tm=(tl+tr)/2;
	build(2*v,tl,tm,a);
	build(2*v+1,tm+1,tr,a);
	Tmx[v]=max(Tmx[2*v],Tmx[2*v+1]);
	Tmn[v]=min(Tmn[2*v],Tmn[2*v+1]);
}
int querymn(int l, int r, int v, int tl, int tr) {
	if(l > r)return 1e9;
	if(l == tl and r == tr)return Tmn[v];
	int tm=(tl+tr)/2;
	return min(querymn(l,min(r,tm),2*v,tl,tm),
			querymn(max(l,tm+1),r,2*v+1,tm+1,tr));
}
int querymx(int l, int r, int v, int tl, int tr) {
	if(l > r)return 1e9;
	if(l == tl and r == tr)return Tmx[v];
	int tm=(tl+tr)/2;
	return max(querymx(l,min(r,tm),2*v,tl,tm),
			querymx(max(l,tm+1),r,2*v+1,tm+1,tr));
}
int hiL(int L) {
	int lo = 0, hi = n-1;
	while(hi-lo>1) { // [lo, hi)
		int mid = (hi+lo)/2;
		if(querymn(mid, n-1, 1, 0, n-1)<=L) {
			lo=mid;
		}
		else {
			hi=mid;
		}
	}
	return lo;
}
int loL(int L) {
	int lo = 0, hi = n-1;
	while(hi-lo>1) { // (lo, hi]
		int mid = (hi+lo)/2;
		if(querymn(0, mid, 1, 0, n-1)<=L) {
			hi=mid;
		}
		else {
			lo=mid;
		}
	}
	return hi;
}
int hiR(int R) {
	int lo = 0, hi = n-1;
	while(hi-lo>1) { // [lo, hi)
		int mid = (hi+lo)/2;
		if(querymx(mid, n-1, 1, 0, n-1)>=R) {
			lo=mid;
		}
		else {
			hi=mid;
		}
	}
	return lo;
}
int loR(int R) {
	int lo = 0, hi = n-1;
	while(hi-lo>1) { // (lo, hi]
		int mid = (hi+lo)/2;
		if(querymx(0, mid, 1, 0, n-1)>=R) {
			hi=mid;
		}
		else {
			lo=mid;
		}
	}
	return hi;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
	std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
	n=N;
  int Q = S.size();
  if(N <= 3000 and Q <= 3000 and Y.size() <= 6000) {
	  std::vector<int> A(Q);
	  for(int j = 0; j < Q; ++j) {
		  DSU l(N+1), r(N+1);
		  for(int i = 0;i<(int)X.size();i++) {
			if(X[i] <= R[j] and Y[i]<=R[j])l.unite(X[i], Y[i]);
			if(X[i]>=L[j] and Y[i]>=L[j])r.unite(X[i], Y[i]);
		  }
		  for(int i = L[j];i<=R[j];i++) {
			if(l.same_set(E[j], i) and r.same_set(S[j],i))A[j]=1;
		  }
	  }
	  return A;
  }
  else {
	for(int i = 0;i<N-1;i++) {
		g[Y[i]].push_back(X[i]);
		g[X[i]].push_back(Y[i]);
	}
	for(int i = 0;i<N;i++) {
		if(g[i].size() == 1){
			dfs(i);
			break;
		}
	}
	build(1, 0, n-1, topo);
	int in[N];
	for(int i = 0;i<N;i++) {
		in[topo[i]]=i;
	}
	vector<int> ans(E.size());
	for(int i = 0;i<E.size();i++) {
		if(in[E[i]] < in[S[i]]) {
			int lr = loR(R[i]), hl=hiL(L[i]);
			if(hl > lr)ans[i]=1;
		}
		else {
			int hr = hiR(R[i]), ll=loL(L[i]);
			if(hr > ll)ans[i]=1;
		}
	}
	return ans;
  }
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:144:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for(int i = 0;i<E.size();i++) {
      |                ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5028 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 4 ms 5036 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5028 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 4 ms 5036 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 375 ms 5312 KB Output is correct
11 Correct 347 ms 5308 KB Output is correct
12 Correct 274 ms 5296 KB Output is correct
13 Correct 397 ms 5300 KB Output is correct
14 Correct 334 ms 5292 KB Output is correct
15 Correct 604 ms 5372 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 768 ms 36680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5028 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 4 ms 5036 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 375 ms 5312 KB Output is correct
11 Correct 347 ms 5308 KB Output is correct
12 Correct 274 ms 5296 KB Output is correct
13 Correct 397 ms 5300 KB Output is correct
14 Correct 334 ms 5292 KB Output is correct
15 Correct 604 ms 5372 KB Output is correct
16 Incorrect 768 ms 36680 KB Output isn't correct
17 Halted 0 ms 0 KB -