Submission #791047

#	Time	Username	Problem	Language	Result	Execution time	Memory
791047		YassirSalama	Werewolf (IOI18_werewolf)	C++14	0 / 100	1173 ms	524288 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define ll long long
#define pb push_back
const int MAXN=2e5;
int tree[4*MAXN][2];
vector<int> euler;
vector<vector<int>> v(MAXN);	
const int INF=1e9;
void build(int node,int l,int r){
	if(l==r){
		tree[node][0]=euler[l];
		tree[node][1]=euler[l];
		return;
	}
	int mid=(l+r)/2;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
	tree[node][0]=min(tree[node<<1][0],tree[node<<1|1][0]);
	tree[node][1]=max(tree[node<<1][1],tree[node<<1|1][1]);
}
int query1(int node,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree[node][0];
	int ans=INF;
	int mid=(l+r)/2;
	if(ql<=mid) ans=min(ans,query1(node<<1,l,mid,ql,qr));
	if(qr>mid) ans=min(ans,query1(node<<1|1,mid+1,r,ql,qr));
	return ans;
}
int query2(int node,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree[node][1];
	int ans=0;
	int mid=(l+r)/2;
	if(ql<=mid) ans=max(ans,query2(node<<1,l,mid,ql,qr));
	if(qr>mid) ans=max(ans,query2(node<<1|1,mid+1,r,ql,qr));
	return ans;
}
void dfs(int node,int par){
	euler.push_back(node);
	for(auto x:v[node]) {
		if(x==par) continue;
		dfs(x,node);
	}
}
vector<int> check_validity(int n, vector<int> a, vector<int> b, 
					vector<int> ql, vector<int> qr,
					vector<int> L, vector<int> R) {
	int q = ql.size();
	for(int i=0;i<a.size();i++){
		v[a[i]].pb(b[i]);
		v[b[i]].pb(a[i]);
	}
	map<int,int> mp;
	for(int i=0;i<n;i++){
		if(v[i].size()==1){
			dfs(i,i);
			break;
		}
	}
	for(int i=0;i<n;i++){
		mp[euler[i]]=i;
	}
	build(1,0,n-1);
	vector<int> anns(q,0);
	for(int j=0;j<q;j++){
		int qql=ql[j];
		int qqr=qr[j];
		if(mp[qql]<mp[qqr]) {
			int l=mp[qql];
			int r=mp[qqr]+1;
			int mid;
			int ans=0;
			while(l<=r){
				mid=(l+r)/2;
				if(query1(1,0,n-1,mp[qql],mid)>=L[j]){
					ans=mid;
					l=mid+1;
				}else r=mid-1;
			}
			anns[j]=(query1(1,0,n-1,mp[qql],l)>=L[j]&&query2(1,0,n-1,l,mp[qqr])<=R[j]);
		}else{
			int l=mp[qqr];
			int r=mp[qql];
			int mid;
			int ans=0;
			while(l<=r){
				mid=(l+r)/2;
				if(query1(1,0,n-1,mid,mp[qql])>=L[j]) {
					ans=mid;
					l=mid+1;
				}else r=mid-1;
			}
			anns[j]=(query1(1,0,n-1,l,mp[qql])>=L[j]&&query2(1,0,n-1,mp[qqr],l)<=R[j]);
		}
	}
	return anns;
}

Compilation message (stderr)

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:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
werewolf.cpp:75:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   75 |    int ans=0;
      |        ^~~
werewolf.cpp:88:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   88 |    int ans=0;
      |        ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51