| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1006572 |
2024-06-24T03:47:41 Z |
irmuun |
Werewolf (IOI18_werewolf) |
C++17 |
|
1049 ms |
524288 KB |
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
struct segtreeMax{
int n;
vector<int>d;
segtreeMax(int n):n(n){
d.resize(4*n);
build(1,0,n-1);
}
void build(int node,int l,int r){
if(l==r){
d[node]=0;
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
}
int query(int node,int l,int r,int L,int R){
if(L>R||l>R||L>r) return 0;
if(L<=l&&r<=R) return d[node];
int mid=(l+r)/2;
return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
}
void update(int node,int l,int r,int pos,int val){
if(r<pos||pos<l) return;
if(l==r){
d[node]=val;
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,pos,val);
update(node*2+1,mid+1,r,pos,val);
d[node]=max(d[node*2],d[node*2+1]);
}
};
struct segtreeMin{
int n;
vector<int>d;
segtreeMin(int n):n(n){
d.resize(4*n);
build(1,0,n-1);
}
void build(int node,int l,int r){
if(l==r){
d[node]=0;
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
}
int query(int node,int l,int r,int L,int R){
if(L>R||l>R||L>r) return n;
if(L<=l&&r<=R) return d[node];
int mid=(l+r)/2;
return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
}
void update(int node,int l,int r,int pos,int val){
if(r<pos||pos<l) return;
if(l==r){
d[node]=val;
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,pos,val);
update(node*2+1,mid+1,r,pos,val);
d[node]=min(d[node*2],d[node*2+1]);
}
};
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
int Q=S.size();
int n=N;
vector<int>can(Q,0);
vector<int>adj[N];
for(int i=0;i<X.size();i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vector<int>pos(N);
int cur=0;
segtreeMax sgmx(N);
segtreeMin sgmn(N);
function <void(int,int)> dfs=[&](int x,int p){
sgmx.update(1,0,n-1,cur,x);
sgmn.update(1,0,n-1,cur,x);
pos[x]=cur;
cur++;
for(int y:adj[x]){
if(y!=p){
dfs(y,x);
}
}
};
for(int i=0;i<N;i++){
if(adj[i].size()==1){
dfs(i,-1);
break;
}
}
for(int i=0;i<Q;i++){
if(pos[E[i]]<=pos[S[i]]){
int l=pos[E[i]],r=n-1,x,y;
while(l<r){
int mid=(l+r+1)/2;
if(sgmn.query(1,0,n-1,pos[E[i]],mid)>=L[i]){
l=mid;
}
else{
r=mid-1;
}
}
x=l;
l=0,r=pos[S[i]];
while(l<r){
int mid=(l+r)/2;
if(sgmx.query(1,0,n-1,mid,pos[S[i]])<=R[i]){
r=mid;
}
else{
l=mid+1;
}
}
y=l;
can[i]=(x>=y);
}
else{
int l=pos[S[i]],r=n-1,x,y;
while(l<r){
int mid=(l+r+1)/2;
if(sgmx.query(1,0,n-1,pos[S[i]],mid)<=R[i]){
l=mid;
}
else{
r=mid-1;
}
}
x=l;
l=0,r=pos[E[i]];
while(l<r){
int mid=(l+r)/2;
if(sgmn.query(1,0,n-1,mid,pos[S[i]])>=L[i]){
r=mid;
}
else{
l=mid+1;
}
}
y=l;
can[i]=(x>=y);
}
}
return can;
}
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:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1049 ms |
47376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
