oj.uz

Submission #1035161

# Submission time Handle Problem Language Result Execution time Memory
1035161 2024-07-26T05:26:09 Z huutuan Werewolf (IOI18_werewolf) C++14
0 / 100
 117 ms 50516 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n;
   vector<int> lab;
   void init(int _n){
      n=_n;
      lab.assign(n+1, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u), v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
      }
   }
   bool check(int u, int v){
      return find_set(u)==find_set(v);
   }
} dsu;

bool check[3000][3000];
vector<int> g[3000];
vector<int> vl[3000], vr[3000];

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R) {
   int M=X.size();
   for (int i=0; i<M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
   int Q=S.size();
   for (int i=0; i<Q; ++i){
      vl[L[i]].push_back(i), vr[R[i]].push_back(i);
      for (int j=0; j<N; ++j) check[i][j]=1;
   }
   dsu.init(N);
   for (int i=N-1; i>=0; --i){
      for (int j:g[i]) if (j>i) dsu.union_sets(i, j);
      for (int j:vl[i]){
         for (int k=i; k<N; ++k) check[j][k]&=dsu.check(S[j], k);
      }
   }
   dsu.init(N);
   for (int i=0; i<N; ++i){
      for (int j:g[i]) if (j<i) dsu.union_sets(i, j);
      for (int j:vr[i]){
         for (int k=0; k<i; ++k) check[j][k]&=dsu.check(E[j], k);
      }
   }
   vector<int> ans(Q);
   for (int i=0; i<Q; ++i) ans[i]=*max_element(check[i]+L[i], check[i]+R[i]+1);
   return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 50516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -