Submission #111454

#	Time	Username	Problem	Language	Result	Execution time	Memory
111454		JustasZ	Werewolf (IOI18_werewolf)	C++14	100 / 100	1291 ms	106804 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>g[maxn];
int par[maxn];
int root(int v)
{
    return v == par[v] ? v : par[v] = root(par[v]);
}
struct tree
{
    int tin[maxn], tout[maxn], tim, anc[maxn][20], to_v[maxn];
    vector<int>adj[maxn];
    tree() = default;
    void add_edge(int fr, int to)
    {
        adj[fr].pb(to);
    }
    void dfs(int v)
    {
        tin[v] = ++tim;
        to_v[tim] = v;
        for(int i = 1; i < 20; i++)
            anc[v][i] = anc[anc[v][i - 1]][i - 1];
        for(int to : adj[v])
        {
            anc[to][0] = v;
            dfs(to);
        }
        tout[v] = tim;
    }
} man, wolf;
int f[maxn];
void add(int i)
{
    for(; i < maxn; i += i & -i)
        f[i]++;
}
int get(int i)
{
    int ret = 0;
    for(; i > 0; i -= i & -i)
        ret += f[i];
    return ret;
}
int get(int l, int r)
{
    return get(r) - get(l - 1);
}
vector<int>check_validity(int n, vector<int>X, vector<int>Y, vector<int>S, vector<int>E, vector<int>L, vector<int>R)
{
    for(int i = 0; i < sz(S); i++)
        ++S[i], ++E[i], ++L[i], ++R[i];
    for(int i = 0; i < sz(X); i++)
    {
        ++X[i], ++Y[i];
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    for(int i = 1; i <= n; i++)
        par[i] = i;
    for(int i = 1; i <= n; i++)
    {
        for(int to : g[i])
        {
            if(to < i && root(to) != i)
            {
                wolf.add_edge(i, root(to));
                par[root(to)] = i;
            }
        }
    }
    for(int i = 1; i <= n; i++)
        par[i] = i;
    for(int i = n; i >= 1; i--)
    {
        for(int to : g[i])
        {
            if(to > i && root(to) != i)
            {
                man.add_edge(i, root(to));
                par[root(to)] = i;
            }
        }
    }
    man.dfs(1);
    wolf.dfs(n);
    for(int i = 0; i < sz(S); i++)
    {
        int v = S[i];
        for(int j = 19; j >= 0; j--)
        {
            if(man.anc[v][j] != 0 && man.anc[v][j] >= L[i])
                v = man.anc[v][j];
        }
        S[i] = v;
        v = E[i];
        for(int j = 19; j >= 0; j--)
        {
            if(wolf.anc[v][j] != 0 && wolf.anc[v][j] <= R[i])
                v = wolf.anc[v][j];
        }
        E[i] = v;
    }
    vector<tuple<int, int, int, int> >que[n + 1];
    vector<int>ans(sz(S));
    for(int i = 0; i < sz(S); i++)
    {
        que[wolf.tin[E[i]] - 1].pb(make_tuple(i, -1, man.tin[S[i]], man.tout[S[i]]));
        que[wolf.tout[E[i]]].pb(make_tuple(i, +1, man.tin[S[i]], man.tout[S[i]]));
    }
    for(int i = 1; i <= n; i++)
    {
        add(man.tin[wolf.to_v[i]]);
        for(auto aa : que[i])
        {
            int id, delta, l, r;
            tie(id, delta, l, r) = aa;
            ans[id] += delta * get(l, r);
        }
    }
    for(int i = 0; i < sz(ans); i++)
        ans[i] = (ans[i] > 0);
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51