| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 304931 | oleh1421 | Werewolf (IOI18_werewolf) | C++17 | 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.
//#define SYS
#ifdef SYS
#include "werewolf.h"
#endif // SYS
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=300010;
int p[N];
int q[N];
int a[N];
int b[N];
int dsu[N];
int get(int x){
if (x==dsu[x]) return x;
return get(dsu[x]);
}
vector<int>cmp[N];
vector<int>g[N];
vector<pair<int,int> >qS[N];
vector<pair<int,int> >qE[N];
int La[N];
int Ra[N];
int Lb[N];
int Rb[N];
int dsu1[N];
int mn[N];
int mx[N];
int get1(int x){
if (dsu1[x]==x) return x;
return dsu1[x]=get1(dsu1[x]);
}
vector<int> check_validity(int N, vector<int> X, std::vector<int> Y,vector<int> S,vector<int> E,vector<int> L, vector<int> R) {
int Q = S.size();
vector<int> Ans(Q,0);
for (int i=0;i<X.size();i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i=0;i<N;i++) dsu[i]=i,cmp[i]={i},p[i]=1;
for (int i=N-1;i>=0;i--){
for (int to:g[i]){
int x=get(i);
int y=get(to);
if (x==y) continue;
if (cmp[x].size()>cmp[y].size()) swap(x,y);
for (int v:cmp[x]){
p[v]+=cmp[y].size();
}
for (int v:cmp[x]){
cmp[y].push_back(v);
}
cmp[x].clear();
dsu[x]=y;
}
}
for (int i=0;i<N;i++) dsu[i]=i,cmp[i]={i},q[i]=1;
for (int i=0;i<N;i++){
for (int to:g[i]){
int x=get(i);
int y=get(to);
if (x==y) continue;
if (cmp[x].size()>cmp[y].size()) swap(x,y);
for (int v:cmp[x]){
q[v]+=cmp[y].size();
}
for (int v:cmp[x]){
cmp[y].push_back(v);
}
cmp[x].clear();
}
}
for (int i=0;i<N;i++){
a[p[i]]=i;
b[q[i]]=i;
}
for (int i=0;i<Q;i++){
qS[L[i]].push_back({S[i],i});
qE[R[i]].push_back({E[i],i});
}
for (int i=0;i<N;i++){
dsu1[i]=i;
mn[i]=p[i];
mx[i]=q[i];
}
for (int i=N-1;i>=0;i--){
for (int to:g[i]){
int x=get1(i);
int y=get1(to);
if (x==y) continue;
mn[y]=min(mn[y],mn[x]);
mx[y]=max(mx[y],mx[x]);
dsu[x]=y;
}
for (auto cur:qS[i]){
La[cur.second]=mn[cur.first];
Ra[cur.second]=mx[cur.first];
}
}
for (int i=0;i<N;i++){
dsu1[i]=i;
mn[i]=p[i];
mx[i]=q[i];
}
for (int i=N-1;i>=0;i--){
for (int to:g[i]){
int x=get1(i);
int y=get1(to);
if (x==y) continue;
mn[y]=min(mn[y],mn[x]);
mx[y]=max(mx[y],mx[x]);
dsu[x]=y;
}
for (auto cur:qS[i]){
La[cur.second]=mn[cur.first];
Ra[cur.second]=mx[cur.first];
}
}
return Ans;
}
#include <cstdio>
#include <cstdlib>
#include <vector>
#ifndef SYS
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
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;
}
#endif