Submission #138079

#	Time	Username	Problem	Language	Result	Execution time	Memory
138079		evpipis	Werewolf (IOI18_werewolf)	C++14	100 / 100	2021 ms	216584 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 2e5+5, lg = 18;
int ord[2][len], par[2][len], st[2][len], en[2][len], dp[2][lg][len];
int anc[len], cnt;
vector<int> adj[2][len], nex[len];

struct node{
    int sum;
    node *lef, *rig;

    node(int s = 0, node *l = NULL, node *r = NULL){
        sum = s;
        lef = l;
        rig = r;
    }
};

typedef node* pnode;
pnode null = new node(), root[len];

pnode upd(pnode t, int l, int r, int i){
    if (l == r)
        return new node(t->sum+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(t->sum+1, upd(t->lef, l, mid, i), t->rig);
    return new node(t->sum+1, t->lef, upd(t->rig, mid+1, r, i));
}

int ask(pnode a, pnode b, int l, int r, int i, int j){
    if (r < i || j < l)
        return 0;
    if (i <= l && r <= j)
        return (a->sum-b->sum);

    int mid = (l+r)/2;
    return ask(a->lef, b->lef, l, mid, i, j) + ask(a->rig, b->rig, mid+1, r, i, j);
}

int fin(int i){
    if (anc[i] == i) return i;
    return anc[i] = fin(anc[i]);
}

void dfs(int u, int t){
    ord[t][++cnt] = u;
    st[t][u] = cnt;

    for (int j = 0; j < adj[t][u].size(); j++){
        int v = adj[t][u][j];
        dfs(v, t);
        par[t][v] = u;
    }

    en[t][u] = cnt;
}

ii sub(int u, int x, int t){
    if (t == 0){
        for (int j = lg-1; j >= 0; j--)
            if (dp[t][j][u] > 0 && dp[t][j][u] >= x)
                u = dp[t][j][u];
    }
    else{
        for (int j = lg-1; j >= 0; j--)
            if (dp[t][j][u] > 0 && dp[t][j][u] <= x)
                u = dp[t][j][u];
    }

    return mp(st[t][u], en[t][u]);
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R){
    int m = X.size(), q = S.size();

    for (int i = 0; i < m; i++){
        int a = X[i]+1, b = Y[i]+1;
        if (a > b)
            swap(a, b);

        nex[a].pb(b);
        nex[b].pb(a);
    }

    for (int i = 1; i <= n; i++)
        anc[i] = i;
    for (int l = n; l >= 1; l--){
        for (int j = 0; j < nex[l].size(); j++){
            int v = nex[l][j];
            if (l <= v && fin(v) != l)
                adj[0][l].pb(fin(v)), anc[fin(v)] = l;
        }
    }

    //for (int i = 1; i <= n; i++)
      //  printf("i = %d, fin = %d\n", i, fin(i));

    for (int i = 1; i <= n; i++)
        anc[i] = i;
    for (int r = 1; r <= n; r++){
        for (int j = 0; j < nex[r].size(); j++){
            int v = nex[r][j];
            if (r >= v && fin(v) != r)
                adj[1][r].pb(fin(v)), anc[fin(v)] = r;
        }
    }

    cnt = 0, dfs(1, 0);
    cnt = 0, dfs(n, 1);

    /*printf("ord0 =\n");
    for (int i = 1; i <= n; i++)
        printf("%d ", ord[0][i]);
    printf("\n");

    printf("ord1 =\n");
    for (int i = 1; i <= n; i++)
        printf("%d ", ord[1][i]);
    printf("\n");*/

    root[0] = null->lef = null->rig = null;
    for (int i = 1; i <= n; i++)
        root[i] = upd(root[i-1], 1, n, st[0][ord[1][i]]);

    for (int t = 0; t < 2; t++)
        for (int i = 1; i <= n; i++)
            dp[t][0][i] = par[t][i];
    for (int t = 0; t < 2; t++)
        for (int j = 1; (1<<j) < n; j++)
            for (int i = 1; i <= n; i++)
                if (dp[t][j-1][i])
                    dp[t][j][i] = dp[t][j-1][dp[t][j-1][i]];

    vector<int> out;
    for (int i = 0; i < q; i++){
        int s = S[i]+1, t = E[i]+1, l = L[i]+1, r = R[i]+1;
        ii ra0 = sub(s, l, 0), ra1 = sub(t, r, 1);
        if (ask(root[ra1.se], root[ra1.fi-1], 1, n, ra0.fi, ra0.se) > 0)
            out.pb(1);
        else
            out.pb(0);
    }
    return out;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[t][u].size(); j++){
                     ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < nex[l].size(); j++){
                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:113:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < nex[r].size(); j++){
                         ~~^~~~~~~~~~~~~~~

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