oj.uz

Submission #791069

# Submission time Handle Problem Language Result Execution time Memory
791069 2023-07-23T11:37:39 Z YassirSalama Werewolf (IOI18_werewolf) C++14
34 / 100
 1500 ms 524288 KB 
#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
#define dbg(x) cout << "[ " << #x << " ] : " << x<<endl;
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];
			int mid;
			int ans=0;
			while(l<r){
				mid=(l+r+1)/2;
				if(query1(1,0,n-1,mp[qql],mid)>=L[j]){
					l=mid;
				}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]) {
					r=mid;
				}else l=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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 45020 KB Output is correct
2 Correct 1332 ms 45044 KB Output is correct
3 Correct 1211 ms 45152 KB Output is correct
4 Correct 1277 ms 45148 KB Output is correct
5 Correct 1306 ms 45148 KB Output is correct
6 Correct 1279 ms 45148 KB Output is correct
7 Correct 1372 ms 45144 KB Output is correct
8 Correct 1208 ms 45144 KB Output is correct
9 Correct 542 ms 45024 KB Output is correct
10 Correct 684 ms 45120 KB Output is correct
11 Correct 831 ms 45144 KB Output is correct
12 Correct 697 ms 45144 KB Output is correct
13 Correct 1483 ms 45144 KB Output is correct
14 Correct 1500 ms 45268 KB Output is correct
15 Correct 1379 ms 45160 KB Output is correct
16 Correct 1327 ms 45148 KB Output is correct
17 Correct 1327 ms 45148 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -