#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#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;})
#define ii pair<int, int>
using namespace std;
const int N = 6e5 + 10;
vector<ii> e1[N], e2[N];
int cnt;
vector<tuple<int, int, int, int> > query[N];
struct kruskal {
int par[20][N], w[N], timer, lst[N];
int st[N], ed[N];
vector<int> ad[N];
int root(int v) {
return par[0][v] < 0 ? v : par[0][v] = root(par[0][v]);
}
void join(int u, int v, int c) {
u = root(u); v = root(v);
if (u == v) return;
++cnt;
ad[cnt].push_back(u);
ad[cnt].push_back(v);
par[0][cnt] = -1; w[cnt] = c;
par[0][u] = cnt; par[0][v] = cnt;
}
void dfs(int u) {
st[u] = ++timer;
lst[timer] = u;
for(int j = 1; j <= 19; j++) par[j][u] = par[j - 1][par[j - 1][u]];
for(int &v : ad[u]) {
par[0][v] = u;
dfs(v);
}
ed[u] = timer;
}
int get(int u, int cost, int type) {
for(int j = 19; j >= 0; j--) {
int p = par[j][u];
if (p <= 0) continue;
if (!type && w[p] <= cost) u = p;
else if (type && w[p] >= cost) u = p;
}
return u;
}
} T[2];
int bit[N];
void up(int pos, int val) {
while (pos <= 6e5) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int ret = 0;
while (pos) {
ret += bit[pos];
pos -= pos & -pos;
}
return ret;
}
int getrange(int l, int r) {
return get(r) - get(l - 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) {
cnt = n - 1;
for(int i = 0; i < x.size(); i++) {
int u = x[i], v = y[i];
e1[min(u, v)].emplace_back(u, v);
e2[max(u, v)].emplace_back(u, v);
}
for(int i = 0; i < n; i++) T[0].par[0][i] = T[1].par[0][i] = -1;
for(int i = 0; i < n; i++) for(auto &it : e2[i]) {
T[0].join(it.fi, it.se, i);
}
for(int i = 0; i <= cnt; i++) if (T[0].par[0][i] < 0) T[0].dfs(i);
for(int i = n - 1; i >= 0; i--) for(auto &it : e1[i]) {
T[1].join(it.fi, it.se, i);
}
for(int i = 0; i <= cnt; i++) if (T[1].par[0][i] < 0) T[1].dfs(i);
vector<int> ans;
ans.resize(s.size());
// for(int i = 1; i <= T[0].timer; i++) cout << T[0].lst[i] << " "; cout << endl;
// for(int i = 1; i <= T[1].timer; i++) cout << T[1].lst[i] << " "; cout << endl;
for(int i = 0; i < s.size(); i++) {
int p1 = T[1].get(s[i], l[i], 1);
int p2 = T[0].get(e[i], r[i], 0);
// cout << p1 << " " << p2 << endl;
// cout << T[1].st[p1] << " " << T[1].ed[p1] << " " << T[0].st[p2] << " " << T[0].ed[p2] << endl;
query[T[1].ed[p1]].emplace_back(T[0].st[p2], T[0].ed[p2], i, 1);
query[T[1].st[p1] - 1].emplace_back(T[0].st[p2], T[0].ed[p2], i, -1);
}
for(int i = 0; i <= T[1].timer; i++) {
int u = T[1].lst[i];
if (u < n) up(T[0].st[u], 1);
for(auto &it : query[i]) {
int L, R, id, sign; tie(L, R, id, sign) = it;
ans[id] += sign * getrange(L, R);
}
}
for(int &i : ans) {
i = (i > 0);
}
return ans;
}
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define pb push_back
#ifdef ngu
#define forv(a, b) for(auto &a : b)
int main() {
#define task "task"
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
vector<int> x,y,st,ed,lf,rt;
int n,m,q; 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";
}
#endif // ngu
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:22: 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:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
71136 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
71180 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
71136 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
71180 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1033 ms |
189004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
71136 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
71180 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
