제출 #383146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383146		mohamedsobhi777	늑대인간 (IOI18_werewolf)	C++14	15 / 100	3013 ms	101704 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51