oj.uz

답안 #791045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791045 2023-07-23T11:21:04 Z YassirSalama 늑대인간 (IOI18_werewolf) C++14
0 / 100
 1202 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
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],ans)>=L[j]&&query2(1,0,n-1,ans,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,ans,mp[qql])>=L[j]&&query2(1,0,n-1,mp[qqr],ans)<=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: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++){
      |              ~^~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 300 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 300 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1202 ms 45148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 300 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -