oj.uz

Submission #83510

# Submission time Handle Problem Language Result Execution time Memory
83510 2018-11-08T14:49:35 Z radoslav11 Werewolf (IOI18_werewolf) C++14
49 / 100
 1326 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);

            st[v].clear();
        }

    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 186 ms 197496 KB Output is correct
2 Correct 189 ms 197496 KB Output is correct
3 Correct 190 ms 197496 KB Output is correct
4 Correct 187 ms 197652 KB Output is correct
5 Correct 187 ms 197704 KB Output is correct
6 Correct 189 ms 197704 KB Output is correct
7 Correct 183 ms 197704 KB Output is correct
8 Correct 190 ms 197804 KB Output is correct
9 Correct 182 ms 197804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 197496 KB Output is correct
2 Correct 189 ms 197496 KB Output is correct
3 Correct 190 ms 197496 KB Output is correct
4 Correct 187 ms 197652 KB Output is correct
5 Correct 187 ms 197704 KB Output is correct
6 Correct 189 ms 197704 KB Output is correct
7 Correct 183 ms 197704 KB Output is correct
8 Correct 190 ms 197804 KB Output is correct
9 Correct 182 ms 197804 KB Output is correct
10 Correct 192 ms 198920 KB Output is correct
11 Correct 193 ms 198920 KB Output is correct
12 Correct 206 ms 199004 KB Output is correct
13 Correct 193 ms 199124 KB Output is correct
14 Correct 195 ms 199352 KB Output is correct
15 Correct 197 ms 199464 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1314 ms 265088 KB Output is correct
2 Correct 1012 ms 271860 KB Output is correct
3 Correct 1020 ms 278448 KB Output is correct
4 Correct 1089 ms 286548 KB Output is correct
5 Correct 1177 ms 295756 KB Output is correct
6 Correct 1245 ms 305844 KB Output is correct
7 Correct 1165 ms 312440 KB Output is correct
8 Correct 992 ms 322420 KB Output is correct
9 Correct 984 ms 326080 KB Output is correct
10 Correct 1008 ms 334100 KB Output is correct
11 Correct 1084 ms 334344 KB Output is correct
12 Correct 1167 ms 344456 KB Output is correct
13 Correct 1037 ms 360052 KB Output is correct
14 Correct 1038 ms 368524 KB Output is correct
15 Correct 1084 ms 376920 KB Output is correct
16 Correct 1217 ms 385416 KB Output is correct
17 Correct 1207 ms 385416 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 197496 KB Output is correct
2 Correct 189 ms 197496 KB Output is correct
3 Correct 190 ms 197496 KB Output is correct
4 Correct 187 ms 197652 KB Output is correct
5 Correct 187 ms 197704 KB Output is correct
6 Correct 189 ms 197704 KB Output is correct
7 Correct 183 ms 197704 KB Output is correct
8 Correct 190 ms 197804 KB Output is correct
9 Correct 182 ms 197804 KB Output is correct
10 Correct 192 ms 198920 KB Output is correct
11 Correct 193 ms 198920 KB Output is correct
12 Correct 206 ms 199004 KB Output is correct
13 Correct 193 ms 199124 KB Output is correct
14 Correct 195 ms 199352 KB Output is correct
15 Correct 197 ms 199464 KB Output is correct
16 Correct 1314 ms 265088 KB Output is correct
17 Correct 1012 ms 271860 KB Output is correct
18 Correct 1020 ms 278448 KB Output is correct
19 Correct 1089 ms 286548 KB Output is correct
20 Correct 1177 ms 295756 KB Output is correct
21 Correct 1245 ms 305844 KB Output is correct
22 Correct 1165 ms 312440 KB Output is correct
23 Correct 992 ms 322420 KB Output is correct
24 Correct 984 ms 326080 KB Output is correct
25 Correct 1008 ms 334100 KB Output is correct
26 Correct 1084 ms 334344 KB Output is correct
27 Correct 1167 ms 344456 KB Output is correct
28 Correct 1037 ms 360052 KB Output is correct
29 Correct 1038 ms 368524 KB Output is correct
30 Correct 1084 ms 376920 KB Output is correct
31 Correct 1217 ms 385416 KB Output is correct
32 Correct 1207 ms 385416 KB Output is correct
33 Correct 1315 ms 385416 KB Output is correct
34 Correct 532 ms 385416 KB Output is correct
35 Correct 1274 ms 406320 KB Output is correct
36 Correct 1282 ms 409088 KB Output is correct
37 Correct 1279 ms 422428 KB Output is correct
38 Correct 1279 ms 427192 KB Output is correct
39 Correct 1226 ms 440892 KB Output is correct
40 Correct 1161 ms 453224 KB Output is correct
41 Correct 1309 ms 456948 KB Output is correct
42 Correct 1195 ms 459992 KB Output is correct
43 Correct 1326 ms 483160 KB Output is correct
44 Correct 1267 ms 485060 KB Output is correct
45 Correct 1164 ms 492172 KB Output is correct
46 Correct 1175 ms 500816 KB Output is correct
47 Correct 1082 ms 517756 KB Output is correct
48 Runtime error 1130 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
49 Halted 0 ms 0 KB -