oj.uz

Submission #1105179

# Submission time Handle Problem Language Result Execution time Memory
1105179 2024-10-25T16:03:51 Z thelegendary08 Werewolf (IOI18_werewolf) C++14
49 / 100
 1877 ms 69352 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(N <= 3000 && m <= 6000 && Q <= 3000){
  	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 182 ms 764 KB Output is correct
11 Correct 92 ms 592 KB Output is correct
12 Correct 18 ms 592 KB Output is correct
13 Correct 204 ms 768 KB Output is correct
14 Correct 108 ms 592 KB Output is correct
15 Correct 176 ms 848 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 60040 KB Output is correct
2 Correct 1756 ms 60312 KB Output is correct
3 Correct 1744 ms 60600 KB Output is correct
4 Correct 1807 ms 60544 KB Output is correct
5 Correct 1787 ms 60056 KB Output is correct
6 Correct 1578 ms 60624 KB Output is correct
7 Correct 1574 ms 60660 KB Output is correct
8 Correct 1557 ms 60056 KB Output is correct
9 Correct 623 ms 60564 KB Output is correct
10 Correct 772 ms 60052 KB Output is correct
11 Correct 1304 ms 60168 KB Output is correct
12 Correct 702 ms 60820 KB Output is correct
13 Correct 1877 ms 60296 KB Output is correct
14 Correct 1856 ms 60356 KB Output is correct
15 Correct 1777 ms 60332 KB Output is correct
16 Correct 1703 ms 60564 KB Output is correct
17 Correct 1533 ms 60044 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 182 ms 764 KB Output is correct
11 Correct 92 ms 592 KB Output is correct
12 Correct 18 ms 592 KB Output is correct
13 Correct 204 ms 768 KB Output is correct
14 Correct 108 ms 592 KB Output is correct
15 Correct 176 ms 848 KB Output is correct
16 Correct 1342 ms 60040 KB Output is correct
17 Correct 1756 ms 60312 KB Output is correct
18 Correct 1744 ms 60600 KB Output is correct
19 Correct 1807 ms 60544 KB Output is correct
20 Correct 1787 ms 60056 KB Output is correct
21 Correct 1578 ms 60624 KB Output is correct
22 Correct 1574 ms 60660 KB Output is correct
23 Correct 1557 ms 60056 KB Output is correct
24 Correct 623 ms 60564 KB Output is correct
25 Correct 772 ms 60052 KB Output is correct
26 Correct 1304 ms 60168 KB Output is correct
27 Correct 702 ms 60820 KB Output is correct
28 Correct 1877 ms 60296 KB Output is correct
29 Correct 1856 ms 60356 KB Output is correct
30 Correct 1777 ms 60332 KB Output is correct
31 Correct 1703 ms 60564 KB Output is correct
32 Correct 1533 ms 60044 KB Output is correct
33 Incorrect 1359 ms 69352 KB Output isn't correct
34 Halted 0 ms 0 KB -