oj.uz

Submission #119419

# Submission time Handle Problem Language Result Execution time Memory
119419 2019-06-21T08:16:07 Z 임유진(#2921) Werewolf (IOI18_werewolf) C++14
34 / 100
 774 ms 34888 KB 
#include "werewolf.h"
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 200005

const int INF=MAXN;
vector<int> e[MAXN];
int dep[MAXN];
bool chk[MAXN];
int mn[MAXN*4], mx[MAXN*4];

void dfs(int x){
	chk[x]=true;
	for(auto a:e[x]) if(!chk[a]){
		dep[a]=dep[x]+1;
		dfs(a);
	}
}

void updseg(int* seg, int idx, int l, int r, int x, int y){
	if(l==r) seg[idx]=y;
	else{
		int m=l+r>>1;
		if(x<=m) updseg(seg, idx*2, l, m, x, y);
		else updseg(seg, idx*2+1, m+1, r, x, y);
		seg[idx]=max(seg[idx*2], seg[idx*2+1]);
	}
}

int gseg(int* seg, int idx, int l, int r, int x, int y){
	if(x<=l&&r<=y) return seg[idx];
	if(r<x||y<l) return -INF;
	int m=l+r>>1;
	return max(gseg(seg, idx*2, l, m, x, y), gseg(seg, idx*2+1, m+1, r, x, y));
}

int glef(int* seg, int idx, int l, int r, int x, int p){
	if(seg[idx]<=p) return l;
	if(l==r) return r+1;
	int m=l+r>>1;
	if(x<=m) return glef(seg, idx*2, l, m, x, p);
	int t=glef(seg, idx*2+1, m+1, r, x, p);
	return t==m+1?glef(seg, idx*2, l, m, x, p):t;
}

int grig(int* seg, int idx, int l, int r, int x, int p){
	if(seg[idx]<=p) return r;
	if(l==r) return l-1;
	int m=l+r>>1;
	if(x>=m) return grig(seg, idx*2+1, m+1, r, x, p);
	int t=grig(seg, idx*2, l, m, x, p);
	return t==m?grig(seg, idx*2+1, m+1, r, x, p):t;
}

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<int> A(Q);
	int h;
	int a, b;
	int hl, hr, wl, wr;

	for(int i=0; i<M; i++){
		e[X[i]].push_back(Y[i]);
		e[Y[i]].push_back(X[i]);
	}
	for(int i=0; i<N; i++) if(e[i].size()==1) h=i;
	dfs(h);

	for(int i=0; i<N; i++){
		updseg(mn, 1, 0, N-1, dep[i], -i);
		updseg(mx, 1, 0, N-1, dep[i], i);
	}

	for(int i=0; i<Q; i++){
		A[i]=0;
		if(S[i]<L[i]||E[i]>R[i]) continue;

		hl=glef(mn, 1, 0, N-1, dep[S[i]], -L[i]);
		hr=grig(mn, 1, 0, N-1, dep[S[i]], -L[i]);
		wl=glef(mx, 1, 0, N-1, dep[E[i]], R[i]);
		wr=grig(mx, 1, 0, N-1, dep[E[i]], R[i]);
		if(hl<=wr&&wl<=hr) A[i]=1;
	}

	return A;
}

Compilation message

werewolf.cpp: In function 'void updseg(int*, int, int, int, int, int)':
werewolf.cpp:26:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1;
         ~^~
werewolf.cpp: In function 'int gseg(int*, int, int, int, int, int)':
werewolf.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
werewolf.cpp: In function 'int glef(int*, int, int, int, int, int)':
werewolf.cpp:43:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
werewolf.cpp: In function 'int grig(int*, int, int, int, int, int)':
werewolf.cpp:52:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
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:62:6: warning: unused variable 'a' [-Wunused-variable]
  int a, b;
      ^
werewolf.cpp:62:9: warning: unused variable 'b' [-Wunused-variable]
  int a, b;
         ^
werewolf.cpp:70:5: warning: 'h' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(h);
  ~~~^~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 32976 KB Output is correct
2 Correct 449 ms 34888 KB Output is correct
3 Correct 562 ms 34680 KB Output is correct
4 Correct 507 ms 34848 KB Output is correct
5 Correct 547 ms 34680 KB Output is correct
6 Correct 596 ms 34728 KB Output is correct
7 Correct 578 ms 34692 KB Output is correct
8 Correct 487 ms 34808 KB Output is correct
9 Correct 488 ms 34680 KB Output is correct
10 Correct 426 ms 34616 KB Output is correct
11 Correct 510 ms 34740 KB Output is correct
12 Correct 453 ms 34552 KB Output is correct
13 Correct 522 ms 34744 KB Output is correct
14 Correct 535 ms 34552 KB Output is correct
15 Correct 530 ms 34616 KB Output is correct
16 Correct 506 ms 34756 KB Output is correct
17 Correct 599 ms 34688 KB Output is correct

Subtask #4
0 / 51.0

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