oj.uz

Submission #383146

# Submission time Handle Problem Language Result Execution time Memory
383146 2021-03-28T22:35:42 Z mohamedsobhi777 Werewolf (IOI18_werewolf) C++14
15 / 100
 3013 ms 101704 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 4e5 + 7;

int n, m, col;
vector<int> le, ri;
int act[N];
vector<int> adj[N];
vector<int> QL[N], QR[N];
int ST[N], EN[N];
int ro1[N], ro2[N];

struct tree
{
       vector<int> adj[N];
       int st[N], en[N], vec[N], t;
       tree() {}
       void dfs(int x, int p)
       {
              st[x] = ++t;
              if (x < n)
                     vec[t] = x;
              else
                     vec[t] = -1;
              for (auto u : adj[x])
              {
                     if (u == p)
                            continue;

                     dfs(u, x);
              }
              en[x] = ++t;
              vec[t] = -1;
       }

       vector<int> inter(int x)
       {
              vector<int> ret;
              for (int i = st[x]; i <= en[x]; ++i)
              {
                     if (~vec[i])
                     {
                            ret.push_back(vec[i]);
                     }
              }
              return ret;
       }
} t1, t2;

struct dsu
{
       int fat[N];
       dsu() { iota(fat, fat + N, 0); }
       int find(int x) { return fat[x] = x == fat[x] ? x : find(fat[x]); }
       void link(int u, int v)
       {
              u = find(u), v = find(v);
              if (u > v)
                     swap(u, v);
              fat[u] = v;
       }
       inline bool same(int u, int v) { return find(u) == find(v); }
} d;

void build(tree &t, int dir)
{
       dsu d;
       int lst = n;
       ++col;
       for (int i = (dir == 1 ? 0 : n - 1); i >= 0 && i < n; i += dir)
       {
              for (auto u : adj[i])
              {
                     if (act[u] == col)
                     {
                            int x = d.find(u);
                            if (!d.same(lst, x))
                            {
                                   t.adj[lst].push_back(x);
                                   d.link(x, lst);
                            }
                     }
              }
              t.adj[lst].push_back(i);
              d.link(i, lst);
              ++lst;
              if (dir == -1)
              {
                     for (auto u : QL[i])
                     {
                            ro1[u] = d.find(ST[u]);
                     }
              }
              else
              {
                     for (auto u : QR[i])
                     {
                            ro2[u] = d.find(EN[u]);
                     }
              }
              act[i] = col;
       }
}

std::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, m = X.size();
       le = X, ri = Y;
       int Q = S.size();
       std::vector<int> A(Q);
       for (int i = 0; i < m; ++i)
       {
              adj[X[i]].push_back(Y[i]);
              adj[Y[i]].push_back(X[i]);
       }
       for (int i = 0; i < Q; ++i)
       {
              QL[L[i]].push_back(i);
              QR[R[i]].push_back(i);
              ST[i] = S[i];
              EN[i] = E[i];
       }
       build(t1, -1);
       build(t2, 1);
       t1.dfs(2 * n - 1, 2 * n - 1), t2.dfs(2 * n - 1, 2 * n - 1);

       for (int i = 0; i < Q; ++i)
       {
              vector<int> v1 = t1.inter(ro1[i]);
              vector<int> v2 = t2.inter(ro2[i]);
              sort(v1.begin(), v1.end());
              for (auto u : v2)
              {
                     if (binary_search(v1.begin(), v1.end(), u))
                     {
                            A[i] = 1;
                            break;
                     }
              }
       }

       return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50540 KB Output is correct
2 Correct 34 ms 50560 KB Output is correct
3 Correct 35 ms 50540 KB Output is correct
4 Correct 34 ms 50540 KB Output is correct
5 Correct 34 ms 50540 KB Output is correct
6 Correct 34 ms 50540 KB Output is correct
7 Correct 35 ms 50540 KB Output is correct
8 Correct 38 ms 50668 KB Output is correct
9 Correct 34 ms 50668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50540 KB Output is correct
2 Correct 34 ms 50560 KB Output is correct
3 Correct 35 ms 50540 KB Output is correct
4 Correct 34 ms 50540 KB Output is correct
5 Correct 34 ms 50540 KB Output is correct
6 Correct 34 ms 50540 KB Output is correct
7 Correct 35 ms 50540 KB Output is correct
8 Correct 38 ms 50668 KB Output is correct
9 Correct 34 ms 50668 KB Output is correct
10 Correct 351 ms 51436 KB Output is correct
11 Correct 272 ms 51436 KB Output is correct
12 Correct 55 ms 51436 KB Output is correct
13 Correct 219 ms 51436 KB Output is correct
14 Correct 95 ms 51436 KB Output is correct
15 Correct 327 ms 51564 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50540 KB Output is correct
2 Correct 34 ms 50560 KB Output is correct
3 Correct 35 ms 50540 KB Output is correct
4 Correct 34 ms 50540 KB Output is correct
5 Correct 34 ms 50540 KB Output is correct
6 Correct 34 ms 50540 KB Output is correct
7 Correct 35 ms 50540 KB Output is correct
8 Correct 38 ms 50668 KB Output is correct
9 Correct 34 ms 50668 KB Output is correct
10 Correct 351 ms 51436 KB Output is correct
11 Correct 272 ms 51436 KB Output is correct
12 Correct 55 ms 51436 KB Output is correct
13 Correct 219 ms 51436 KB Output is correct
14 Correct 95 ms 51436 KB Output is correct
15 Correct 327 ms 51564 KB Output is correct
16 Incorrect 3013 ms 101704 KB Output isn't correct
17 Halted 0 ms 0 KB -