Submission #305514

#	Time	Username	Problem	Language	Result	Execution time	Memory
305514		oleh1421	Werewolf (IOI18_werewolf)	C++17	100 / 100	956 ms	104940 KiB

werewolf

#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]);
}
int sum[N];
vector<int>dec1[N];
vector<int>add[N];
int BIT[N];
void upd(int n,int pos,int x){
    for (;pos<=n;pos|=pos+1){
        BIT[pos]+=x;
    }
}
int get_sum(int pos){
    int sum=0;
    for (;pos>=0;pos&=pos+1,pos--){
        sum+=BIT[pos];
    }
    return sum;
}
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]=0;
    for (int i=N-1;i>=0;i--){
        for (int to:g[i]){
            if (to<i) continue;
            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]=0;
    for (int i=0;i<N;i++){
        for (int to:g[i]){
            if (to>i) continue;
            int x=get(i);
            int y=get(to);
            if (x==y) continue;
//            cout<<"edge: "<<to<<" "<<i<<" "<<x<<" "<<y<<" "<<cmp[x].size()<<" "<<cmp[y].size()<<endl;

            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();
            dsu[x]=y;

        }
//        for (int j=0;j<N;j++) cout<<q[j]<<" ";
//        cout<<endl;
    }

    for (int i=0;i<N;i++){
//        cout<<p[i]<<" "<<q[i]<<endl;
        a[p[i]]=i;
        b[q[i]]=i;
    }
//    for (int i=0;i<N;i++) cout<<a[i]<<" ";
//    cout<<endl;
//    for (int i=0;i<N;i++) cout<<b[i]<<" ";
//    cout<<endl;
    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]=p[i];
    }
    for (int i=N-1;i>=0;i--){
        for (int to:g[i]){
            if (to<i) continue;
            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]);
            dsu1[x]=y;
        }
        for (auto cur:qS[i]){
            La[cur.second]=mn[get1(cur.first)];
            Ra[cur.second]=mx[get1(cur.first)];
        }
    }
    for (int i=0;i<N;i++){
        dsu1[i]=i;
        mn[i]=q[i];
        mx[i]=q[i];
    }
    for (int i=0;i<N;i++){
        for (int to:g[i]){
            if (to>i) continue;
            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]);
            dsu1[x]=y;
        }
        for (auto cur:qE[i]){
            Lb[cur.second]=mn[get1(cur.first)];
            Rb[cur.second]=mx[get1(cur.first)];
        }
    }
    for (int i=0;i<Q;i++){
        if (La[i]){
            dec1[La[i]-1].push_back(i);
        }
        add[Ra[i]].push_back(i);
    }
    for (int i=0;i<N;i++){
        upd(N,q[a[i]],1);
        for (int j:dec1[i]){
            sum[j]-=get_sum(Rb[j])-get_sum(Lb[j]-1);
        }
        for (int j:add[i]){
            sum[j]+=get_sum(Rb[j])-get_sum(Lb[j]-1);
        }
    }
    for (int i=0;i<Q;i++){
        Ans[i]=(sum[i]>0);
    }
//    for (int i=0;i<Q;i++){
//        Ans[i]=0;
//        set<int>st;
//        for (int j=La[i];j<=Ra[i];j++){
//            st.insert(a[j]);
//        }
//        for (int j=Lb[i];j<=Rb[i];j++){
//            if (st.find(b[j])!=st.end()) Ans[i]=1;
//        }
//    }
    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
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

*/

Compilation message (stderr)

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:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i=0;i<X.size();i++){
      |                  ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51