oj.uz

Submission #282932

# Submission time Handle Problem Language Result Execution time Memory
282932 2020-08-25T07:28:06 Z milleniumEeee Werewolf (IOI18_werewolf) C++14
15 / 100
 371 ms 54008 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
typedef vector<int> vi;

const int MAXN = (int)2e5 + 5;
const int MAXM = (int)4e5 + 5;
const int MAXQ = (int)2e5 + 5;

vector <int> g[MAXN];
int N, M, Q;

struct Query {
  int s, e, l, r; 
  Query (int s_, int e_, int l_, int r_) {
    s = s_, e = e_, l = l_, r = r_;
  }
  Query () {

  }
}query[MAXQ];

struct Small_Solve {
  bool need = false;
  vector <int> ans;
  void solve() {
    ans.resize(Q, 0);
    vector <int> used[3];
    used[1].resize(N, 0);
    used[2].resize(N, 0);
    int cnt = 0;
    for (int i = 0; i < Q; i++) {
      cnt++;
      queue <int> q[3];
      if (query[i].s >= query[i].l) {
        q[1].push(query[i].s);
      }
      if (query[i].e <= query[i].r) {
        q[2].push(query[i].e);
      }
      while (!q[1].empty()) {
        int v = q[1].front();
        q[1].pop();
        if (used[1][v] == cnt) {
          continue;
        }
        used[1][v] = cnt;
        for (int to : g[v]) {
          if (to >= query[i].l) {
            q[1].push(to);
          }
        }
      }
      while (!q[2].empty()) {
        int v = q[2].front();
        q[2].pop();
        if (used[2][v] == cnt) {
          continue;
        }
        used[2][v] = cnt;
        for (int to : g[v]) {
          if (to <= query[i].r) {
            q[2].push(to);
          }
        }
      }
      int found = 0;
      for (int v = 0; v < N; v++) {
        found |= (used[1][v] == cnt && used[2][v] == cnt);
      }
      ans[i] = found;
    }
  }
}subtask12;

bool bambook() {
  return false;
}

std::vector<int> check_validity(int NN, vi X, vi Y, vi S, vi E, vi L, vi R) {
  N = NN;
  M = szof(X);
  Q = szof(S);
  for (int i = 0; i < M; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < Q; i++) {
    query[i] = Query(S[i], E[i], L[i], R[i]);
  }
  if (N <= 3000 && M <= 6000 && Q <= 3000) {
    subtask12.need = true;
    subtask12.solve();
    return subtask12.ans;
  }
  else if (bambook() == true) {
    
  }
  assert(false);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 339 ms 5504 KB Output is correct
11 Correct 225 ms 5492 KB Output is correct
12 Correct 25 ms 5504 KB Output is correct
13 Correct 371 ms 5624 KB Output is correct
14 Correct 266 ms 5488 KB Output is correct
15 Correct 299 ms 5624 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 339 ms 5504 KB Output is correct
11 Correct 225 ms 5492 KB Output is correct
12 Correct 25 ms 5504 KB Output is correct
13 Correct 371 ms 5624 KB Output is correct
14 Correct 266 ms 5488 KB Output is correct
15 Correct 299 ms 5624 KB Output is correct
16 Runtime error 342 ms 54008 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -