| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1085219 |
2024-09-07T17:19:53 Z |
ASN49K |
Werewolf (IOI18_werewolf) |
C++14 |
|
1743 ms |
250300 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
using namespace std;
struct query
{
int x,y,val_l,val_r,ind,pointer1,pointer2;
};
const int N=200'000,UNSET=-1;
int n,q;
vector<int>adj[N];
vector<query>querys;
set<int>aint[2*N+1];
int lsb(int x,int y)
{
return x&(-x);
}
void add(int x,int y)
{
for(int i=x+n;i>0;i>>=1)
{
aint[i].insert(y);
}
}
bool is_point(int x1,int x2,int y1,int y2)
{
x1+=n;
x2+=n;
for(;x1<=x2;x1>>=1,x2>>=1)
{
if(x1&1)
{
if(aint[x1].lower_bound(y1)!=aint[x1].upper_bound(y2))
{
return true;
}
x1++;
}
if(!(x2&1))
{
if(aint[x2].lower_bound(y1)!=aint[x2].upper_bound(y2))
{
return true;
}
x2--;
}
}
return false;
}
struct Dsu
{
int size_dsu,acm;
vector<int>t,l_child,r_child,l,r,poz;
void init(int n)
{
this->size_dsu=n;
this->acm=-1;
t.resize(2*n);
poz.resize(n);
l_child=r_child=l=r=vector<int>(2*n,0);
iota(all(t) , 0);
}
int root(int x)
{
if(t[x]!=x)
{
t[x]=root(t[x]);
}
return t[x];
}
void unite(int x,int y)
{
x=root(x);
y=root(y);
if(x!=y)
{
l_child[size_dsu]=x;
r_child[size_dsu]=y;
t[x]=t[y]=size_dsu++;
}
}
void dfs(int nod)
{
if(nod<n)
{
cout<<"da";
l[nod]=r[nod]=++acm;
poz[nod]=acm;
}
else
{
dfs(l_child[nod]);
dfs(r_child[nod]);
l[nod]=l[l_child[nod]];
r[nod]=r[r_child[nod]];
}
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R)
{
n=N;
q=(int)L.size();
vector<int>rez(q);
for(int i=0;i<(int)X.size();i++)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
querys.resize(q);
querys.shrink_to_fit();
for(int i=0;i<q;i++) {
assert(S[i] >= L[i] && E[i] <= R[i]);
querys[i] = {S[i], E[i], L[i], R[i], i, UNSET ,UNSET};
}
Dsu dsu[2];
dsu[0].init(n);
sort(all(querys),[&](const query& a,const query& b){
return a.val_l>b.val_l;
});
int last=n;
for(auto &c:querys)
{
while(last>c.val_l)
{
last--;
for(auto &v:adj[last])
{
if(last<v)
{
dsu[0].unite(v,last);
}
}
}
c.pointer1=dsu[0].root(c.x);
}
while(last>-1)
{
last--;
for(auto &v:adj[last])
{
if(last<v)
{
dsu[0].unite(v,last);
}
}
}
dsu[1].init(n);
sort(all(querys),[&](const query& a,const query& b){
return a.val_r<b.val_r;
});
last=-1;
for(auto &c:querys)
{
while(last<c.val_r)
{
last++;
for(auto &v:adj[last])
{
if(v<last)
{
dsu[1].unite(v,last);
}
}
}
c.pointer2=dsu[1].root(c.y);
}
while(last<n-1)
{
last++;
for(auto &v:adj[last])
{
if(v<last)
{
dsu[1].unite(v,last);
}
}
}
dsu[0].dfs(2*n-2);
dsu[1].dfs(2*n-2);
for(int i=0;i<n;i++)
{
add(dsu[0].poz[i] , dsu[1].poz[i]);
cout<<dsu[0].poz[i]<<' '<<dsu[1].poz[i]<<'\n';
}
for(auto &c:querys)
{
//l in loc de r
rez[c.ind]=is_point(dsu[0].l[c.pointer1],dsu[0].r[c.pointer1],dsu[1].l[c.pointer2],dsu[1].r[c.pointer2]);
}
return rez;
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1743 ms |
250300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
