Submission #787379

#	Time	Username	Problem	Language	Result	Execution time	Memory
787379		boyliguanhan	Werewolf (IOI18_werewolf)	C++17	100 / 100	1808 ms	272768 KiB

werewolf

#include "werewolf.h"
#define pb push_back
#define VI vector<int>
#include<bits/stdc++.h>
using namespace std;
#define MXN 400100
struct node{
    int l,r,val,lc,rc;
    node():l(0){}
    node(int l, int r, int val, int lc, int rc):l(l),r(r),val(val),lc(lc),rc(rc){}
    node(int pos):l(pos),r(pos),val(1){}
} t[15*MXN];
int cnt;
int query(int i, int l, int r) {
    if(!t[i].val||t[i].l>r||t[i].r<l)return 0;
    if(l<=t[i].l&&t[i].r<=r) return t[i].val;
    return query(t[i].lc,l,r)+query(t[i].rc,l,r);
}
int mn(int a, int b) {
    t[++cnt] = node(t[a].l,t[b].r,t[a].val+t[b].val,a,b);
    return cnt;
}
int upd(int i, int pos) {
    if(t[i].l==t[i].r) {
        t[++cnt] = node(pos);
        return cnt;
    }
    if(pos<t[t[i].rc].l)
        return mn(upd(t[i].lc,pos),t[i].rc);
    return mn(t[i].lc, upd(t[i].rc, pos));
}
int build(int l, int r){
    if(l==r) return t[++cnt]=node(l,l,0,0,0),cnt;
    return mn(build(l,l+r>>1),build(l+r+2>>1,r));
}
int order[2][MXN], times[4][MXN], cntx, p[MXN], tb[2][20][MXN], cnty;
int abp(int n) {
    return (p[n]==n)?n:(p[n]=abp(p[n]));
}
VI adj[4][MXN];
void dfs1(int n) {
    order[0][times[0][n]=++cntx] = n;
    for(auto i: adj[0][n])
        dfs1(i);
    times[2][n] = cntx;
}
void dfs2(int n) {
    order[1][times[1][n]=++cntx] = n;
    for(auto i: adj[1][n])
        dfs2(i);
    times[3][n] = cntx;
}
VI rt;
VI check_validity(int N,VI X,VI Y,VI s,VI e,VI l,VI r){
    VI ans;     
    for(int i = 0; i < X.size(); i++) {
        if(X[i] < Y[i])
            adj[2][X[i]].pb(Y[i]),
            adj[3][Y[i]].pb(X[i]);
        else
            adj[3][X[i]].pb(Y[i]),
            adj[2][Y[i]].pb(X[i]);
    }
    iota(p, p+MXN, 0);
    for(int i = N; i--;) {
        for(auto j: adj[2][i]) {
            if(abp(j)!=i) {
                adj[0][i].pb(p[j]);
                tb[0][0][p[j]] = i;
                p[p[j]]=i;
            }
        }
    }
    iota(p, p+MXN, 0);
    for(int i = 0; i < N; i++) {
        for(auto j: adj[3][i]) {
            if(abp(j)!=i) {
                adj[1][i].pb(p[j]);
                tb[1][0][p[j]] = i;
                p[p[j]]=i;
            }
        }
    }
    tb[1][0][N-1] = tb[1][0][N] = N;
    for(int i = 1; i < 20; i++)
        for(int j = 0; j < 2*N; j++)
            tb[0][i][j] = tb[0][i-1][tb[0][i-1][j]], tb[1][i][j] = tb[1][i-1][tb[1][i-1][j]];
    dfs1(0);
    cntx=0;
    dfs2(N-1);
    rt.pb(build(1,N));
    for(int i = 1; i <= N; i++) {
        rt.pb(upd(rt.back(), times[1][order[0][i]]));
    }
    for(int i = 0; i < s.size(); i++) {
        int a = s[i], b = e[i], c = l[i], d = r[i];
        for(int i = 20; i--;) {
            if(tb[0][i][a]>=c)
                a = tb[0][i][a];
            if(tb[1][i][b]<=d)
                b = tb[1][i][b];
        }
        int A,B,C,D;
        A = times[0][a];
        B = times[2][a];
        C = times[1][b];
        D = times[3][b];
        ans.pb((bool)(query(rt[B], C, D) - query(rt[A-1],C,D)));
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'int build(int, int)':
werewolf.cpp:34:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     return mn(build(l,l+r>>1),build(l+r+2>>1,r));
      |                       ~^~
werewolf.cpp:34:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     return mn(build(l,l+r>>1),build(l+r+2>>1,r));
      |                                     ~~~^~
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:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 0; i < X.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

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