Submission #305067

#	Time	Username	Problem	Language	Result	Execution time	Memory
305067		oleh1421	Werewolf (IOI18_werewolf)	C++17	0 / 100	734 ms	81252 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]);
}
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]){
            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++) cout<<p[i]<<" ";
//        cout<<endl;
    }
    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]){
            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]){
                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++){
//        cout<<p[i]<<" "<<q[i]<<endl;
        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]=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[cur.first];
            Ra[cur.second]=mx[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[cur.first];
            Rb[cur.second]=mx[cur.first];
        }
    }
    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() {
//    printf("%d\n",);
//  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(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
#endif
/*


*/

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

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