#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) cout<<__LINE__<<": "<<#__VA_ARGS__<<"- ",_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cout<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cout<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
int n;
vector<int> g[maxn];
struct dsu{
int par[maxn], sz[maxn];
// vector<int> tree[maxn];
vector<vector<int> > tree;
int L[maxn], R[maxn];
vector<int> ord;
int IT;
int find(int x) {return x == par[x]? x : par[x] = find(par[x]); }
// int findrng(int x, int l, int r) {
// if (x == par[x] || par[x] > r || par[x] < l) return x;
// return findrng(x,l,r);
// }
void mrg(int a, int b) { // b is the new parent
a = find(a); b = find(b);
if (a == b) return;
// if (sz[a] > sz[b]) swap(a,b);
par[a]=b; tree[b].pb(a);
// sz[b] += sz[a];
}
// void buildtree(){
// REP(i,n) {
// tree[par[i]].pb(i);
// }
// }
bool seen[maxn];
void dfs(int v) {
seen[v] = 1;
ord.pb(v);
L[v] = R[v] = IT++;
for (int u : tree[v]) {
dfs(u);
R[v] = R[u];
}
}
// void rundfs() {
// REP(i,n) {
// if (!seen[i]) dfs(i);
// }
// }
dsu(){
tree.resize(n);
REP(i,maxn) par[i] = i, sz[i] = 1;
IT = 0;
}
};
vector<int> ret;
vector<int> rbhere[maxn], lbhere[maxn]; // which queries have respective bounds here
int sub1[maxn], sub2[maxn]; // which subtree do you govern?
int seg[maxn];
void MO(int e, int v) {
for (++e; e<maxn; e+=e&-e) seg[e] += v;
}
int QU(int e) {
int re=0;
for (++e; e>0; e-=e&-e) re += seg[e];
return re;
}
struct qq{
// int cnt; // count under this
int l, r, i, dir;
};
vector<qq> go[maxn];
vector<int> check_validity(int _n, vector<int> mx, vector<int> my, vector<int> S, vector<int> E, vector<int> LB, vector<int> RB) {
n = _n;
cout<<"yo"<<endl;
// return {1,0,0};
// cout<<"yo"<<endl;
// return {0,0,0};
// bug("hi");
REP(i ,SZ(mx)) {
g[mx[i]].pb(my[i]);
g[my[i]].pb(mx[i]);
}
int q = SZ(S);
ret.resize(q);
REP(i,q) {
rbhere[RB[i]].pb(i);
lbhere[LB[i]].pb(i);
}
dsu LT, RT;
// build first tree from left
REP(i, n) {
for (int v : g[i]) {
if ( v<i)
LT.mrg(v, i); // order matters here! i is the new root
}
for (int y : rbhere[i]) {
sub1[y] = LT.find(E[y]);
}
}
// return {};
LT.dfs(n-1);
for (int i = n-1; i>=0; --i) {
for (int v : g[i]) {
if (v > i)
RT.mrg(v,i);
}
for (int y : lbhere[i]) {
sub2[y] = RT.find(S[y]);
// cout<<"tree 2: "<<y<<' '<<S[y]<<' '<<sub2[y]<<endl;
}
}
RT.dfs(0);
// cout<<"Tree 2: "<<endl;
// REP(i,n) cout<<RT.ord[i]<<' ';
// cout<<endl;
// vector<qq> ev;
REP(i, q) {
int lw = LT.L[sub1[i]], rw = LT.R[sub1[i]];
int qlw = RT.L[sub2[i]], qrw = RT.R[sub2[i]];
if (lw-1>=0) go[lw-1].pb({qlw, qrw, i, -1});
go[rw].pb({qlw, qrw, i, 1});
}
REP(i, n) {
int pos = RT.L[LT.ord[i]];
// cout<<"pos: "<<pos<<' '<<LT.ord[i]<<endl;
MO(pos, 1);
for (qq e : go[i]) {
ret[e.i] += e.dir * (QU(e.r) - QU(e.l-1));
}
}
REP(i, q) {
ret[i] = min(ret[i], 1);
}
return ret;
}
//#undef BALBIT
//signed main(){
// IOS();
//
//
//}
//#enidf
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
593 ms |
80524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
