oj.uz

Submission #305080

# Submission time Handle Problem Language Result Execution time Memory
305080 2020-09-22T14:25:11 Z oleh1421 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 88480 KB 
#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]=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++){
        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

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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 19 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 19 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28672 KB Output is correct
10 Correct 813 ms 29516 KB Output is correct
11 Correct 570 ms 29512 KB Output is correct
12 Correct 53 ms 29568 KB Output is correct
13 Correct 456 ms 29516 KB Output is correct
14 Correct 77 ms 29440 KB Output is correct
15 Correct 500 ms 29560 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 88480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 19 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28672 KB Output is correct
10 Correct 813 ms 29516 KB Output is correct
11 Correct 570 ms 29512 KB Output is correct
12 Correct 53 ms 29568 KB Output is correct
13 Correct 456 ms 29516 KB Output is correct
14 Correct 77 ms 29440 KB Output is correct
15 Correct 500 ms 29560 KB Output is correct
16 Execution timed out 4075 ms 88480 KB Time limit exceeded
17 Halted 0 ms 0 KB -