oj.uz

Submission #1105178

# Submission time Handle Problem Language Result Execution time Memory
1105178 2024-10-25T16:02:27 Z thelegendary08 Werewolf (IOI18_werewolf) C++14
34 / 100
 1856 ms 69088 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
using namespace std;
const int mxn = 200005;
int tree[mxn*4][2];
int n;
bool intersect(pair<int,int>a, pair<int,int>b){
	if(a.first > b.first)swap(a,b);
	if(a.first > a.second || b.first > b.second)return false;
	if(a.second < b.first)return false;
	else return true;
}
int quer(int l, int r, int d){
	l += n;
	r+=n;
	int s = 0;
	while(l<=r){
		if(l % 2 == 1)s += tree[l++][d];
		if(r % 2 == 0)s += tree[r--][d];
		l/=2;
		r/=2;
	}
	return s;
}
void upd(int k, int x, int d){
	k += n;
	tree[k][d] = x;
	for(k/=2; k>=1; k/=2){
		tree[k][d] = tree[k*2][d] + tree[k*2+1][d];
	}
}
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();
  int m = X.size();
  vector<int>adj[N];
  f0r(i, m){
  	adj[X[i]].pb(Y[i]);
  	adj[Y[i]].pb(X[i]);
  }
  vector<int>ans(Q);
  //N <= 3000 && m <= 6000 && Q <= 3000
  if(false){
  	f0r(t, Q){
	  	int s = S[t];
	  	int e = E[t];
	  	int l = L[t];
	  	int r = R[t];
	  	vector<bool>vis(N, 0);
	  	vector<bool>wis(N, 0);
	  	
	  	queue<int>q;
	  	if(s >= l){
	  		vis[s] = 1;
	  		q.push(s);
	  	}
	  	while(!q.empty()){
	  		int node = q.front();
	  		q.pop();
	  		for(auto u : adj[node]){
	  			if(vis[u])continue;
	  			if(u < l)continue;
	  			vis[u] = 1;
	  			q.push(u);
	  		}
	  	}
	  	
	  	if(e <= r){
	  		wis[e] = 1;
	  		q.push(e);
	  	}
	  	while(!q.empty()){
	  		int node = q.front();
	  		q.pop();
	  		for(auto u : adj[node]){
	  			if(wis[u])continue;
	  			if(u > r)continue;
	  			wis[u] = 1;
	  			q.push(u);
	  		}
	  	}
	  	int a = 0;
	  	f0r(i,N){
	  		if(vis[i] && wis[i])a = 1;
	  	}
	  	ans[t] = a;
	  }
	  
	  return ans;
  }
  else{
  	int fi;
  	f0r(i,N){
  		if(adj[i].size() == 1)fi = i;
  	}
  	vi dex;
  	dex.pb(fi);
  	vector<bool>vis(N, 0);
  	vis[fi] = 1;
  	queue<int>q;
  	q.push(fi);
  	while(!q.empty()){
  		int node = q.front();
  		q.pop();
  		for(auto u : adj[node]){
  			if(vis[u])continue;
  			vis[u] = 1;
  			dex.pb(u);
  			q.push(u);
  		}
  	}
  	
  	vi invmap(N);
  	f0r(i, N){
  		invmap[dex[i]] = i;
  	}
  	vector<vi>lefts;
  	vector<vi>rights;
  	f0r(i, Q){
  		lefts.pb({L[i], invmap[S[i]], i});
  		rights.pb({R[i], invmap[E[i]], i});
  	}
  	sort(lefts.begin(), lefts.end());
  	sort(rights.rbegin(), rights.rend());
  	//for(auto u : invmap)cout<<u<<' ';
  	//cout<<'\n';
  	
  	f0r(i, n){
  		upd(i, 1, 0);
  		upd(i, 1, 1);
  	}
  	
  	int cur = -1;
  	vector<pair<int,pair<int,int>>>la;
  	vector<pair<int,pair<int,int>>>ra;
  	
  	f0r(i,Q){
  		if(lefts[i][0]-1 > cur){
  			for(int j = cur + 1; j <= lefts[i][0]-1; j++){
  				upd(invmap[j], 0, 0);
  			}
  			cur = lefts[i][0]-1;
  			
  			
  		}
  		f0r(j, n){
  			//cout<<tree[j+n][0]<<' ';
  		}
  		//cout<<'\n';
  		//f0r(j,3)cout<<lefts[i][j]<<' ';
  		//cout<<'\n';
  		//bs the first index in [l, N] to have a 0
  		int l = lefts[i][1];
  		int lo = l;
		int hi = N;
		//cout<<lo<<' '<<hi<<'\n';
		while(lo < hi){
			//cout<<lo<<' '<<hi<<'\n';
			int mid = lo + (hi - lo)/2;
			if(quer(l, mid, 0) < mid - l + 1){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
			
		}
		int lo2 = -1;
		int hi2 = l;
		while(lo2 < hi2){
			int mid = lo2 + (hi2 - lo2 + 1)/2;
			if(quer(mid, l, 0) < l - mid + 1){
				lo2 = mid;
			}
			else{
				hi2 = mid - 1;
			}
		}
		la.pb({lefts[i][2], {lo2+1, lo-1}});
  	}
  	
  	cur = N;
  	f0r(i,Q){
  		if(rights[i][0]+1 < cur){
  			for(int j = cur - 1; j >= rights[i][0]+1; j--){
  				upd(invmap[j], 0, 1);
  			}
  			cur = rights[i][0]+1;
  		}
  		//bs the last index in [-1, r] to have a 0
  		int r = rights[i][1];
  		int lo = -1;
		int hi = r;
		while(lo < hi){
			int mid = lo + (hi - lo + 1)/2;
			if(quer(mid, r, 1) < r - mid + 1){
				lo = mid;
			}
			else{
				hi = mid - 1;
			}
		}
		int lo2 = r;
		int hi2 = n;
		while(lo2 < hi2){
			int mid = lo2 + (hi2 - lo2)/2;
			if(quer(r, mid, 1) < mid - r + 1){
				hi2 = mid;
			}
			
			else{
				lo2 = mid + 1;
			}
		}
		ra.pb({rights[i][2], {lo+1, lo2-1}});
  	}
  	sort(la.begin(), la.end());
  	sort(ra.begin(), ra.end());
  	//for(auto u : la)cout<<u.second.first<<' '<<u.second.second<<' ';
  	//cout<<'\n';
  	//for(auto u : ra)cout<<u.second.first<<' '<<u.second.second<<' ';
  	//cout<<'\n';
  	vi ans(Q);
  	f0r(i, Q){
  		if(intersect(la[i].second, ra[i].second))ans[i] = 1;
  		else ans[i] = 0;
  	}
  	return ans;
  	
  	//return {};
  }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 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 1391 ms 60308 KB Output is correct
2 Correct 1849 ms 68716 KB Output is correct
3 Correct 1727 ms 68984 KB Output is correct
4 Correct 1754 ms 68528 KB Output is correct
5 Correct 1823 ms 69000 KB Output is correct
6 Correct 1576 ms 68356 KB Output is correct
7 Correct 1633 ms 68576 KB Output is correct
8 Correct 1668 ms 68708 KB Output is correct
9 Correct 595 ms 68500 KB Output is correct
10 Correct 792 ms 68412 KB Output is correct
11 Correct 1226 ms 68756 KB Output is correct
12 Correct 707 ms 69020 KB Output is correct
13 Correct 1849 ms 68464 KB Output is correct
14 Correct 1856 ms 68460 KB Output is correct
15 Correct 1855 ms 69016 KB Output is correct
16 Correct 1838 ms 69032 KB Output is correct
17 Correct 1464 ms 69088 KB Output is correct

Subtask #4
0 / 51.0

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