| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 726000 | Cookie | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "werewolf.h"
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const int mxn = 7e5;
int pl[mxn + 1], pr[mxn + 1], n;
vt<int>adj[mxn + 1], adjl[mxn + 1], adjr[mxn + 1];
vt<pii>ql[mxn + 1], qr[mxn + 1];
int tonodel[mxn + 1], tonoder[mxn + 1], tt = 0;
int tinl[mxn + 1], toutl[mxn + 1], tinr[mxn + 1], toutr[mxn + 1], rootl[mxn + 1], rootr[mxn + 1];
int fpl(int u){
if(pl[u] == u)return(u);
return(pl[u] = fpl(pl[u]));
}
int fpr(int u){
if(pr[u] == u)return(u);
return(pr[u] = fpr(pr[u]));
}
void unonl(int u, int v){
v = fpl(v);
if(u == v)return;
pl[v] = u; adjl[u].pb(v);
}
void unonr(int u, int v){
v = fpr(v);
if(u == v)return;
pr[v] = u; adjr[u].pb(v);
}
void dfsl(int s){
if(s < n){
tinl[s] = ++tt; tonodel[tt] = s;
}
else tinl[s] = 2 * n;
for(auto i: adjl[s]){
dfsl(i); tinl[s] = min(tinl[s], tinl[i]);
}
toutl[s] = tt;
}
void buildl(){
for(int i = 0; i < n; i++)pl[i] = i;
for(int i = n - 1; i >= 0; i--){
int pos = n + i;
pl[pos] = pos;
unonl(pos, i);
for(auto j: adj[i]){
if(j > i){
unonl(pos, j);
}
}
for(auto [u, id]: ql[i]){
int U = fpl(u); rootl[id] = U;
}
}
pl[2 * n] = 2 * n;
for(int i = 0; i <= n - 1; i++){
unonl(2 * n, i);
}
dfsl(2 * n);
}
void dfsr(int s){
if(s < n){
tinr[s] = ++tt; tonoder[tt] = s;
}
else tinr[s] = 2 * n;
for(auto i: adjr[s]){
dfsr(i); tinr[s] = min(tinr[s], tinr[i]);
}
toutr[s] = tt;
}
void buildr(){
for(int i = 0; i < n; i++)pr[i] = i;
for(int i = 0; i < n; i++){
int pos = n + i; pr[pos] = pos;
unonr(pos, i);
for(auto j: adjr[i]){
if(j < i){
unonr(pos, j);
}
}
for(auto [u, id]: qr[i]){
int U = fpr(u);
rootr[id] = U;
}
}
tt = 0; pr[2 * n] = 2 * n;
for(int i = 0; i < n; i++){
unonr(2 * n, i);
}
dfsr(2 * n);
}
struct Events{
int type, y, l, r, id;
bool operator <(const Events &b){
if(y == b.y){
return(type > b.type);
}
return(y < b.y);
}
};
int bit[mxn + 1], before[mxn + 1], after[mxn + 1];
void upd(int p, int v){
while(p <= mxn){
bit[p] += v;
p += p & (-p);
}
}
int get(int p){
int ans = 0;
while(p){
ans += bit[p];
p -= p & (-p);
}
return(ans);
}
vt<Events>events;
vt<int>check_validity(int N, vt<int>x, vt<int>y, vt<int>s, vt<int>e, vt<int>l, vt<int>r){
n = N;
for(int i = 0; i < x.size(); i++){
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
for(int i = 0; i < l.size(); i++){
ql[l[i]].pb(make_pair(s[i], i));
qr[r[i]].pb(make_pair(e[i], i));
}
buildl();
buildr();
for(int i = 0; i < l.size(); i++){
events.pb({1, tinr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
events.pb({-1, toutr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
}
for(int i = 0; i < n; i++){
events.pb({0, tinr[i], tinl[i], -1, -1});
}
sort(events.begin(), events.end());
for(auto [type, y, l, r, id]: events){
if(type == 0){
upd(l, 1);
}else if(type == 1){
before[id] = get(r) - get(l - 1);
}else{
after[id] = get(r) - get(l - 1);
}
}
vt<int>ans;
for(int i = 0; i < l.size(); i++){
ans.pb((bool)(before[i] < after[i]));
}
return(ans);
}
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}