oj.uz

Submission #83508

# Submission time Handle Problem Language Result Execution time Memory
83508 2018-11-08T14:47:27 Z radoslav11 Werewolf (IOI18_werewolf) C++14
15 / 100
 2330 ms 525312 KB 
/*
    We build a prefix and suffix tree with dsu, by incrementing them by 1 vertex at each step. Now queries become:
    Do two subtrees have a common vertex (the first subtree is from the prefix tree and the second subtree is from the suffix tree).
    This can be done with DFS order + dsu on tree by keeping a set for each vertex. The complexity will be O(N log^2 N + Q log N).
*/

#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()

using namespace std;
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int tp[MAXN], sz[MAXN], par[MAXN];

void init(int n)
{
    for(int i = 0; i <= n; i++)
        par[i] = i, sz[i] = 1, tp[i] = i;
}

int root(int x) { return x == par[x] ? x : (par[x] = root(par[x])); }

bool connected(int u, int v)
{
    return root(u) == root(v);
}

void unite(int u, int v)
{
    u = root(u), v = root(v);
    if(u == v) return;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

struct Tree
{
    vector<int> adj[MAXN];
    int st[MAXN], en[MAXN], dfs_time;

    void add_edge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void pre_dfs(int u, int pr)
    {
        st[u] = ++dfs_time;
        for(int v: adj[u])
            if(v != pr)
                pre_dfs(v, u);
        en[u] = dfs_time;
    }

    void order(int root)
    {
        dfs_time = 0;
        pre_dfs(root, root);
    }
} t1, t2;

vector<int> adj[MAXN];
vector<int> pref[MAXN], suff[MAXN];
vector<int> ans;
int vert1[MAXN], vert2[MAXN];

set<int> st[MAXN];
vector<int> que[MAXN];

void solve(int u, int pr = -1)
{
    st[u].insert(t1.st[u]);
    for(int v: t2.adj[u])
        if(v != pr)
        {
            solve(v, u);
            if(st[u].size() > st[v].size()) swap(st[u], st[v]);

            for(int x: st[v])
                st[u].insert(x);
        }

    for(int i: que[u])
    {
        int L = t1.st[vert1[i]], R = t1.en[vert1[i]];

        auto it = st[u].lower_bound(L);
        if(it != st[u].end() && *it <= R)
            ans[i] = 1;
    }
}

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)
{
    int q = S.size(), m = X.size();
    ans.assign(q, 0);

    for(int i = 0; i < m; i++)
    {
        int u = X[i], v = Y[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 0; i < q; i++)
    {
        suff[L[i]].push_back(i);
        pref[R[i]].push_back(i);
    }

    init(n);
    for(int i = 0; i < n; i++)
    {
        for(int v: adj[i])
            if(i > v)
                if(!connected(i, v))
                {
                    t1.add_edge(tp[root(i)], tp[root(v)]);
                    unite(i, v);
                    tp[root(i)] = i;
                }

        for(int it: pref[i])
            vert1[it] = tp[root(E[it])];
    }

    int r1 = tp[root(0)];
    t1.order(r1);

    init(n);
    for(int i = n - 1; i >= 0; i--)
    {
        for(int v: adj[i])
            if(i < v)
                if(!connected(i, v))
                {
                    t2.add_edge(tp[root(i)], tp[root(v)]);
                    unite(i, v);
                    tp[root(i)] = i;
                }

        for(int it: suff[i])
            vert2[it] = tp[root(S[it])];
    }

    int r2 = tp[root(0)];
    t2.order(r2);

    for(int i = 0; i < q; i++)
        que[vert2[i]].push_back(i);

    solve(r2);

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 197624 KB Output is correct
2 Correct 176 ms 197624 KB Output is correct
3 Correct 190 ms 197628 KB Output is correct
4 Correct 178 ms 197628 KB Output is correct
5 Correct 189 ms 197788 KB Output is correct
6 Correct 179 ms 197792 KB Output is correct
7 Correct 177 ms 197800 KB Output is correct
8 Correct 173 ms 197800 KB Output is correct
9 Correct 180 ms 197880 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 197624 KB Output is correct
2 Correct 176 ms 197624 KB Output is correct
3 Correct 190 ms 197628 KB Output is correct
4 Correct 178 ms 197628 KB Output is correct
5 Correct 189 ms 197788 KB Output is correct
6 Correct 179 ms 197792 KB Output is correct
7 Correct 177 ms 197800 KB Output is correct
8 Correct 173 ms 197800 KB Output is correct
9 Correct 180 ms 197880 KB Output is correct
10 Correct 591 ms 305812 KB Output is correct
11 Correct 402 ms 305812 KB Output is correct
12 Correct 202 ms 305812 KB Output is correct
13 Correct 397 ms 305812 KB Output is correct
14 Correct 207 ms 305812 KB Output is correct
15 Correct 411 ms 305812 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2330 ms 507752 KB Output is correct
2 Runtime error 1484 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 197624 KB Output is correct
2 Correct 176 ms 197624 KB Output is correct
3 Correct 190 ms 197628 KB Output is correct
4 Correct 178 ms 197628 KB Output is correct
5 Correct 189 ms 197788 KB Output is correct
6 Correct 179 ms 197792 KB Output is correct
7 Correct 177 ms 197800 KB Output is correct
8 Correct 173 ms 197800 KB Output is correct
9 Correct 180 ms 197880 KB Output is correct
10 Correct 591 ms 305812 KB Output is correct
11 Correct 402 ms 305812 KB Output is correct
12 Correct 202 ms 305812 KB Output is correct
13 Correct 397 ms 305812 KB Output is correct
14 Correct 207 ms 305812 KB Output is correct
15 Correct 411 ms 305812 KB Output is correct
16 Correct 2330 ms 507752 KB Output is correct
17 Runtime error 1484 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -