| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 759303 |
2023-06-16T05:25:47 Z |
Khizri |
Werewolf (IOI18_werewolf) |
C++17 |
|
1869 ms |
83460 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,q,m,x[mxn],y[mxn],a[mxn],b[mxn],color[3005],color2[3005],idx[mxn],arr[mxn];
pii tree[4*mxn];
vector<int>vt[mxn];
void build(int node,int l,int r){
if(l==r){
tree[node].F=arr[l];
tree[node].S=arr[l];
return;
}
int m=(l+r)/2;
build(2*node,l,m);
build(2*node+1,m+1,r);
tree[node].F=min(tree[2*node].F,tree[2*node+1].F);
tree[node].S=max(tree[2*node].S,tree[2*node+1].S);
}
pii query(int node,int l,int r,int ql,int qr){
if(l>qr||r<ql){
pii ans;
ans.F=n+5;
ans.S=-5;
return ans;
}
if(ql<=l&&r<=qr) return tree[node];
int m=(l+r)/2;
pii x=query(2*node,l,m,ql,qr);
pii y=query(2*node+1,m+1,r,ql,qr);
pii ans;
ans.F=min(x.F,y.F);
ans.S=max(x.S,y.S);
return ans;
}
void dfs(int u,int l,int r){
if(u<l||u>r) return;
color[u]=1;
for(int v:vt[u]){
if(!color[v]&&v>=l&&v<=r){
dfs(v,l,r);
}
}
}
void dfs2(int u,int l,int r){
if(u<l||u>r) return;
color2[u]=1;
for(int v:vt[u]){
if(!color2[v]&&v>=l&&v<=r){
dfs2(v,l,r);
}
}
}
void give_idx(int u,int p,int id){
idx[u]=id;
arr[id]=u;
for(int v:vt[u]){
if(v!=p){
give_idx(v,u,id+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) {
n=N;
m=X.size();
q=S.size();
for(int i=0;i<X.size();i++){
vt[X[i]+1].pb(Y[i]+1);
vt[Y[i]+1].pb(X[i]+1);
}
for(int i=0;i<S.size();i++){
x[i+1]=S[i]+1;
y[i+1]=E[i]+1;
a[i+1]=L[i]+1;
b[i+1]=R[i]+1;
}
vector<int>ans;
if(n<=3000&&m>=6000&&q<=3000){
for(int i=1;i<=q;i++){
memset(color,0,sizeof(color));
memset(color2,0,sizeof(color2));
dfs(x[i],a[i],n);
dfs2(y[i],1,b[i]);
int ok=0;
for(int j=a[i];j<=b[i];j++){
if(color[j]&&color2[j]){
ok=1;
break;
}
}
if(ok){
ans.pb(1);
}
else{
ans.pb(0);
}
}
return ans;
}
int st=0;
for(int i=n;i>=1;i--){
if(vt[i].size()==1){
st=i;
break;
}
}
give_idx(st,-1,1);
build(1,1,n);
//cout<<1<<endl;
for(int i=1;i<=q;i++){
int s=idx[x[i]],e=idx[y[i]];
//cout<<s<<' '<<e<<endl;
int p=0;
if(s>e){
swap(s,e);
p=1;
}
if(!p){
int l=s,r=e;
while(l<=r){
int m=(l+r)/2;
if(query(1,1,n,s,m).F>=a[i]){
l=m+1;
}
else{
r=m-1;
}
}
int pos=l-1;
l=s,r=e;
while(l<=r){
int m=(l+r)/2;
if(query(1,1,n,m,e).S<=b[i]){
r=m-1;
}
else{
l=m+1;
}
}
int pos2=r+1;
//cout<<pos<<' '<<pos2<<endl;
if(pos2<=pos){
ans.pb(1);
}
else{
ans.pb(0);
}
}
else{
int l=s,r=e;
while(l<=r){
int m=(l+r)/2;
if(query(1,1,n,s,m).S<=b[i]){
l=m+1;
}
else{
r=m-1;
}
}
int pos=l-1;
l=s,r=e;
while(l<=r){
int m=(l+r)/2;
if(query(1,1,n,m,e).F>=a[i]){
r=m-1;
}
else{
l=m+1;
}
}
int pos2=r+1;
//cout<<pos<<' '<<pos2<<endl;
if(pos2<=pos){
ans.pb(1);
}
else{
ans.pb(0);
}
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
-------
5 4 1
0 1
1 2
2 3
3 4
1 3 1 2
--
6 5 3
0 4
4 3
3 1
1 2
2 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
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:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
83460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
83460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1608 ms |
35788 KB |
Output is correct |
| 2 |
Correct |
1869 ms |
44248 KB |
Output is correct |
| 3 |
Correct |
1869 ms |
44172 KB |
Output is correct |
| 4 |
Correct |
1830 ms |
44320 KB |
Output is correct |
| 5 |
Correct |
1803 ms |
44192 KB |
Output is correct |
| 6 |
Correct |
1708 ms |
44340 KB |
Output is correct |
| 7 |
Correct |
1813 ms |
44196 KB |
Output is correct |
| 8 |
Correct |
1798 ms |
44288 KB |
Output is correct |
| 9 |
Correct |
783 ms |
44244 KB |
Output is correct |
| 10 |
Correct |
947 ms |
44160 KB |
Output is correct |
| 11 |
Correct |
1124 ms |
44184 KB |
Output is correct |
| 12 |
Correct |
1338 ms |
44280 KB |
Output is correct |
| 13 |
Correct |
1843 ms |
44200 KB |
Output is correct |
| 14 |
Correct |
1854 ms |
44168 KB |
Output is correct |
| 15 |
Correct |
1844 ms |
44192 KB |
Output is correct |
| 16 |
Correct |
1796 ms |
44232 KB |
Output is correct |
| 17 |
Correct |
1796 ms |
44264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
83460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
