#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
const int N=2010;
int n,m,q;
struct pack{
int u,v,c;
};
struct kruskal{
int dir, tim, it;
vector<pack> edg;
vector<int> ad[N];
vector<int> id,st,ed,val,pos;
vector<vector<int>> f;
int root(int x){
return id[x]==x? x : id[x]=root(id[x]);
}
void dfs(int u,int p=-1){
st[u]=++tim; pos[tim]=u;
forinc(i,1,20)
f[u][i]=f[f[u][i-1]][i-1];
forv(v,ad[u]) if(v!=p){
f[v][0]=u;
dfs(v,u);
}
ed[u]=tim;
}
ii que(int u,int x){
if((dir && u>x) || (!dir && u<x)) return {n+n,n+n};
if((dir && val[f[u][0]]>x) || (!dir && val[f[u][0]]<x)) return {st[u],ed[u]};
u=f[u][0];
fordec(i,20,0)
if((dir && val[f[u][i]]<=x) || (!dir && val[f[u][i]]>=x)) u=f[u][i];
return {st[u],ed[u]};
}
void build(int dire){ dir=dire;
id.resize(N), st.resize(N), ed.resize(N), val.resize(N), f.resize(N), pos.resize(N);
forv(i,f) i.resize(22);
sort(all(edg),[](pack i,pack j){
return i.c>j.c;
});
if(dir) reverse(all(edg));
int it=n-1;
forinc(i,1,n+n) id[i]=i;
forv(i,edg){
int u=i.u,
v=i.v,
c=i.c,
x=root(u),
y=root(v);
if(x==y) continue;
val[it+1]=c;
ad[it+1].pb(x);
ad[it+1].pb(y);
id[x]=id[y]=++it;
}
dfs(f[it][0]=it);
}
}pf,sf;
int T[N*4];
void upd(int s,int l,int r,int i){
if(l>i||i>r) return;
if(l==r){
T[s]++;
return;
}
int m=(l+r)/2;
upd(2*s,l,m,i); upd(2*s+1,m+1,r,i);
T[s]=T[2*s]+T[2*s+1];
}
int que(int s,int l,int r,int u,int v){
if(l>v||u>r) return 0;
if(u<=l&&r<=v)
return T[s];
int m=(l+r)/2;
return que(2*s,l,m,u,v)+que(2*s+1,m+1,r,u,v);
}
vector<ii> qry[N];
ii range[N];
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> st,vector<int> ed,vector<int> lf,vector<int> rt){
m=x.size(), q=st.size();
vector<int> ans(q);
forinc(i,0,m-1){
sf.edg.pb({x[i],y[i],max(x[i],y[i])});
pf.edg.pb({x[i],y[i],min(x[i],y[i])});
}
return ans;
sf.build(1);
pf.build(0);
forinc(i,0,q-1){
ii u=pf.que(st[i],lf[i]);
ii v=sf.que(ed[i],rt[i]);
//cerr<<u.fi<<" "<<v.fi<<"\n";
//cerr<<u.se<<" "<<v.se<<"\n";
if(u.fi<n+n && v.fi<n+n){
range[i]=v;
qry[u.fi-1].pb({i,-1});
qry[u.se].pb({i,1});
}
}
forinc(i,1,n+n-1){
if(pf.pos[i]<n) upd(1,0,n+n,sf.st[pf.pos[i]]);
forv(j,qry[i]){
//cerr<<range[j.fi].fi<<" "<<range[j.fi].se<<"\n";
ans[j.fi]+=j.se * que(1,0,n+n,range[j.fi].fi,range[j.fi].se);
}
}
forv(i,ans) i=!!i;
return ans;
}
/**
main(){
#define task "WEREWOLF"
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
vector<int> x,y,st,ed,lf,rt;
cin>>n>>m>>q;
forinc(i,1,m){
x.pb(in),y.pb(in);
}
forinc(i,1,q){
st.pb(in), ed.pb(in), lf.pb(in), rt.pb(in);
}
forv(i,check_validity(n,x,y,st,ed,lf,rt)) cout<<i<<"\n";
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
15768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
