oj.uz

답안 #119411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119411 2019-06-21T07:58:13 Z 임유진(#2921) 늑대인간 (IOI18_werewolf) C++14
0 / 100
 417 ms 32772 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));
}

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;

		/*
		a=0, b=dep[S[i]];
		while(a<b){
			int m=a+b>>1;
			if(gseg(mn, 1, 0, N-1, m, dep[S[i]])<=-L[i]) b=m;
			else a=m+1;
		}
		hl=a;

		a=dep[S[i]], b=N-1;
		while(a<b){
			int m=a+b+1>>1;
			if(gseg(mn, 1, 0, N-1, dep[S[i]], m)<=-L[i]) a=m;
			else b=m-1;
		}
		hr=a;

		a=0, b=dep[E[i]];
		while(a<b){
			int m=a+b>>1;
			if(gseg(mx, 1, 0, N-1, m, dep[E[i]])<=R[i]) b=m;
			else a=m+1;
		}
		wl=a;

		a=dep[E[i]], b=N-1;
		while(a<b){
			int m=a+b+1>>1;
			if(gseg(mx, 1, 0, N-1, dep[E[i]], m)<=R[i]) a=m;
			else b=m-1;
		}
		wr=a;

		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 '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:44:6: warning: unused variable 'a' [-Wunused-variable]
  int a, b;
      ^
werewolf.cpp:44:9: warning: unused variable 'b' [-Wunused-variable]
  int a, b;
         ^
werewolf.cpp:45:6: warning: unused variable 'hl' [-Wunused-variable]
  int hl, hr, wl, wr;
      ^~
werewolf.cpp:45:10: warning: unused variable 'hr' [-Wunused-variable]
  int hl, hr, wl, wr;
          ^~
werewolf.cpp:45:14: warning: unused variable 'wl' [-Wunused-variable]
  int hl, hr, wl, wr;
              ^~
werewolf.cpp:45:18: warning: unused variable 'wr' [-Wunused-variable]
  int hl, hr, wl, wr;
                  ^~
werewolf.cpp:52:5: warning: 'h' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(h);
  ~~~^~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 417 ms 32772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5092 KB Output isn't correct
2 Halted 0 ms 0 KB -