oj.uz

Submission #1038811

# Submission time Handle Problem Language Result Execution time Memory
1038811 2024-07-30T07:51:45 Z Mr_Husanboy Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 22400 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){return a.size();}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct DSU{
  vector<int> par, sz; int n;
  DSU (int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }
  DSU (){}
  int get(int a){
    return (par[a] == a ? a : par[a] = get(par[a]));
  }

  void init(int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }

  void unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    par[b] = a;
  }

  void link(int a, int b){
    a = get(a); b = get(b);
    if(a == b) return;
    sz[b] += sz[a];
    par[a] = b;
  }
};

int n, m, q;
vector<vector<int>> g;

vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> l, std::vector<int> r) {
  n = N;
  q = len(s);
  m = len(x);
  vector<int> res(q);
  for(int i = 0; i < m; i ++) if(x[i] > y[i]) swap(x[i], y[i]);

  for(int i = 0; i < q; i ++){
    DSU hum(n), wolf(n);
    for(int j = 0; j < m; j ++){
      if(x[j] >= l[i]){
        hum.unite(y[j], x[j]);
       // cout << x[j] << ' ' << y[j];
      }
      if(y[j] <= r[i]){
        wolf.unite(x[j], y[j]);
      }
    }
    //cout << endl;
    bool ok = 0;
    for(int j = l[i]; j <= r[i]; j ++){
      if(hum.get(j) != hum.get(s[i])) continue;
      if(wolf.get(j) != wolf.get(e[i])) continue;
      ok = 1;
      break;
    }
    res[i] = ok;
  }
  return res; 
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 241 ms 736 KB Output is correct
11 Correct 247 ms 740 KB Output is correct
12 Correct 241 ms 604 KB Output is correct
13 Correct 208 ms 724 KB Output is correct
14 Correct 193 ms 712 KB Output is correct
15 Correct 295 ms 604 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 241 ms 736 KB Output is correct
11 Correct 247 ms 740 KB Output is correct
12 Correct 241 ms 604 KB Output is correct
13 Correct 208 ms 724 KB Output is correct
14 Correct 193 ms 712 KB Output is correct
15 Correct 295 ms 604 KB Output is correct
16 Execution timed out 4061 ms 22400 KB Time limit exceeded
17 Halted 0 ms 0 KB -