oj.uz

Submission #138188

# Submission time Handle Problem Language Result Execution time Memory
138188 2019-07-29T14:29:32 Z wzy Werewolf (IOI18_werewolf) C++11
34 / 100
 2480 ms 44744 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
bool vis[N];
int Lx , Rx;
vector<int> adj[N];
vector<int> v;
int nx ; 
int pos[N];
void solve(int x ){
	v.push_back(x);
	vis[x] = true;
	for(auto w : adj[x]){
		if(!vis[w]){
			solve(w);
		}
	}
}

struct node{
	int minvl , maxvl;
} st[4*N];

node merge(node a , node b){
	node x;
	x.minvl = min(a.minvl , b.minvl);
	x.maxvl = max(a.maxvl , b.maxvl);
	return x;
}

void build(int l = 0 , int r = nx - 1 , int curr = 1){
	// cout<<l<<" " <<r <<" " << curr << endl;
	int mid =  (l+r)/2;
	if(l == r){
		st[curr].minvl = st[curr].maxvl = v[l];
		return ;
	}
	build(l , mid , 2*curr);
	build(mid + 1 , r , 2*curr + 1);
	st[curr] = merge(st[2*curr] , st[2*curr + 1]);
}

node query(int x , int y , int  l = 0 , int r = nx -1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return st[curr];
	}
	if(y <= mid){
		return query(x,y,l,mid,2*curr);
	}
	else if(x > mid){
		return query(x,y,mid+1 , r , 2*curr +1);
	}
	else{
		return merge(query(x,mid,l,mid,2*curr) , query(mid + 1 , y , mid + 1 , r , 2*curr + 1));
	}
}



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) {
  nx = N ;
  for(int i = 0 ; i < X.size() ; i ++){
  	adj[X[i]].push_back(Y[i]);
  	adj[Y[i]].push_back(X[i]);
  }  
  for(int i = 0 ; i < N ; i ++){
  	if(adj[i].size() == 1){
  		solve(i);
  		break;
  	}
  }
  for(int i = 0 ; i < N ; i ++){
  	pos[v[i]] = i;
  }
  build();
  int Q = S.size();
  std::vector<int> A(Q, 0);
  for(int i = 0; i < Q; ++i) {
    if(pos[S[i]] < pos[E[i]]){
    	int l = pos[S[i]] , r = pos[E[i]];
    	int ansj = l;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(pos[S[i]] , mid).minvl < L[i]){
    			r = mid - 1;
    		}
    		else{
    			l = mid + 1;
    			ansj = mid;
    		}
    	}
    	l = pos[S[i]] , r = pos[E[i]];
    	int ansj2 = r;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(mid , pos[E[i]]).maxvl > R[i]){
    			l = mid + 1;
    		}
    		else{
    			r = mid - 1;
    			ansj2 = mid;
    		}
    	}
    	if(ansj >= ansj2){
    		A[i] = 1;
    	}
    }
    else{
    	int l = pos[E[i]] , r = pos[S[i]];
    	int ansj = l;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(pos[E[i]] , mid).maxvl > R[i]){
    			r = mid - 1;
    		}
    		else{
    			l = mid + 1;
    			ansj = mid;
    		}
    	}
    	l = pos[E[i]] , r = pos[S[i]];
    	int ansj2 = r;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(mid , pos[S[i]]).minvl < L[i]){
    			l = mid + 1;
    		}
    		else{
    			r = mid - 1;
    			ansj2 = mid;
    		}
    	}
    	if(ansj >= ansj2){
    		A[i] = 1;
    	}    	
    }
  }
  return A;
}

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:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < X.size() ; i ++){
                   ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 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 5112 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 2058 ms 37100 KB Output is correct
2 Correct 2366 ms 44620 KB Output is correct
3 Correct 2480 ms 44744 KB Output is correct
4 Correct 2316 ms 44656 KB Output is correct
5 Correct 2260 ms 44652 KB Output is correct
6 Correct 2169 ms 44652 KB Output is correct
7 Correct 2251 ms 44548 KB Output is correct
8 Correct 2298 ms 44532 KB Output is correct
9 Correct 946 ms 44268 KB Output is correct
10 Correct 1072 ms 44372 KB Output is correct
11 Correct 1219 ms 44332 KB Output is correct
12 Correct 1440 ms 44412 KB Output is correct
13 Correct 2365 ms 44244 KB Output is correct
14 Correct 2356 ms 44268 KB Output is correct
15 Correct 2357 ms 44052 KB Output is correct
16 Correct 2335 ms 44012 KB Output is correct
17 Correct 2272 ms 44016 KB Output is correct

Subtask #4
0 / 51.0

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