| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 853626 |
2023-09-24T18:24:37 Z |
errw |
Werewolf (IOI18_werewolf) |
C++14 |
|
524 ms |
125740 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
int n,m,q,p[200001],node[200001],l[400001],r[400001],par[400001][20],val[400001],id,x[200001],idx,order[200001];
int lx[200001],rx[200001],ly[200001],ry[200001];
vector <int> ke[400001],a,st[800001];
vector <pii> edge;
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
int w=i;
i=f(i);
j=f(j);
if (i==j)
return;
id++;
val[id]=w;
ke[id].push_back(node[i]);
ke[id].push_back(node[j]);
node[i]=id;
p[j]=i;
}
void dfs(int u){
if (u<n){
l[u]=r[u]=x[u]=idx;
idx++;
return;
}
l[u]=1e9,r[u]=0;
for (int v:ke[u]){
par[v+1][0]=u+1;
for (int i=1;i<20;i++)
par[v+1][i]=par[par[v+1][i-1]][i-1];
dfs(v);
l[u]=min(l[u],l[v]);
r[u]=max(r[u],r[v]);
}
}
void build(int node, int l, int r){
if (l==r){
st[node]={x[order[l]]};
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
int i=0,j=0;
while (i<st[node<<1].size()||j<st[node<<1|1].size()){
if (i>=st[node<<1].size()){
st[node].push_back(st[node<<1|1][j]);
j++;
continue;
}
if (j>=st[node<<1|1].size()){
st[node].push_back(st[node<<1][i]);
i++;
continue;
}
if (st[node<<1][i]<st[node<<1|1][j]){
st[node].push_back(st[node<<1][i]);
i++;
continue;
}
st[node].push_back(st[node<<1|1][j]);
j++;
continue;
}
}
int get(int node, int l, int r, int u, int v, int y){
if (l>v||r<u||l>r||u>v)
return 0;
if (l>=u&&r<=v)
return upper_bound(st[node].begin(),st[node].end(),y)-st[node].begin();
int mid=(l+r)>>1;
return get(node<<1,l,mid,u,v,y)+get(node<<1|1,mid+1,r,u,v,y);
}
bool get(int l, int r, int x, int y){
return get(1,0,n-1,l,r,y)-get(1,0,n-1,l,r,x-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){
m=X.size();
q=S.size();
a.assign(q,0);
iota(p,p+n,0);
iota(node,node+n,0);
id=n;
for (int i=0;i<m;i++)
edge.push_back({min(X[i],Y[i]),max(X[i],Y[i])});
sort(edge.begin(),edge.end());
for (int i=m-1;i>=0;i--)
unite(edge[i].first,edge[i].second);
dfs(id);
for (int i=0;i<q;i++){
int u=S[i]+1;
for (int j=19;j>=0;j--)
if (par[u][j]&&val[par[u][j]-1]>=L[i])
u=par[u][j];
lx[i]=l[u-1];
rx[i]=r[u-1];
}
for (int i=0;i<n;i++){
order[x[i]]=i;
node[i]=p[i]=i;
}
for (int i=0;i<=id;i++)
ke[i].clear();
id=n;
idx=0;
for (int i=0;i<m;i++)
swap(edge[i].first,edge[i].second);
sort(edge.begin(),edge.end());
for (int i=0;i<m;i++)
unite(edge[i].first,edge[i].second);
dfs(id);
for (int i=0;i<q;i++){
int u=E[i]+1;
for (int j=19;j>=0;j--)
if (par[u][j]&&val[par[u][j]-1]<=R[i])
u=par[u][j];
ly[i]=l[u-1];
ry[i]=r[u-1];
}
build(1,0,n-1);
for (int i=0;i<q;i++)
a[i]=get(lx[i],rx[i],ly[i],ry[i]);
return a;
}
Compilation message
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while (i<st[node<<1].size()||j<st[node<<1|1].size()){
| ~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:50:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while (i<st[node<<1].size()||j<st[node<<1|1].size()){
| ~^~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if (i>=st[node<<1].size()){
| ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (j>=st[node<<1|1].size()){
| ~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
41560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
41560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
524 ms |
125740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
41560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
