Submission #153110

#	Time	Username	Problem	Language	Result	Execution time	Memory
153110		arnold518	Werewolf (IOI18_werewolf)	C++14	100 / 100	2091 ms	156208 KiB

werewolf

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXQ = 2e5;

int N, M, Q;
vector<int> S, E, L, R, ans;

struct UF
{
    int par[MAXN+10];
    void init() { for(int i=0; i<N; i++) par[i]=i; }
    int Find(int x) { return (x==par[x])?x:(par[x]=Find(par[x])); }
}uf1, uf2;

vector<int> adj[MAXN+10], adj1[MAXN+10], adj2[MAXN+10];
int s1[MAXN+10], e1[MAXN+10], s2[MAXN+10], e2[MAXN+10], cnt;
int par1[MAXN+10][25], par2[MAXN+10][25];

void dfs(int now, int *s, int *e, vector<int> *adj)
{
    s[now]=cnt++; e[now]=s[now];
    for(int nxt : adj[now])
    {
        dfs(nxt, s, e, adj);
        e[now]=max(e[now], e[nxt]);
    }
}

int A[MAXN+10];
vector<int> tree[4*MAXN+10];
void init(int node, int tl, int tr)
{
    if(tl==tr)
    {
        tree[node].push_back(A[tl]);
        return;
    }
    int mid=tl+tr>>1;
    init(node*2, tl, mid);
    init(node*2+1, mid+1, tr);
    tree[node].resize(tree[node*2].size()+tree[node*2+1].size());
    merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin());
}

int query(int node, int tl, int tr, int xl, int xr, int yl, int yr)
{
    if(tr<xl || xr<tl) return 0;
    if(xl<=tl && tr<=xr) return upper_bound(tree[node].begin(), tree[node].end(), yr)-lower_bound(tree[node].begin(), tree[node].end(), yl);
    int mid=tl+tr>>1;
    return query(node*2, tl, mid, xl, xr, yl, yr)+query(node*2+1, mid+1, tr, xl, xr, yl, yr);
}

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 i, j;
    N=_N; S=_S; E=_E; L=_L; R=_R; M=X.size(), Q=S.size(); ans.resize(Q);

    for(i=0; i<M; i++)
    {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    uf1.init(); par1[0][0]=0;
    for(i=N-1; i>=0; i--)
    {
        int now=i;
        for(int nxt : adj[now])
        {
            if(nxt<now) continue;
            nxt=uf1.Find(nxt);
            if(now==nxt) continue;
            uf1.par[nxt]=now; par1[nxt][0]=now;
            adj1[now].push_back(nxt);
        }
    }

    uf2.init(); par2[N-1][0]=N-1;
    for(i=0; i<N; i++)
    {
        int now=i;
        for(int nxt : adj[now])
        {
            if(nxt>now) continue;
            nxt=uf2.Find(nxt);
            if(now==nxt) continue;
            uf2.par[nxt]=now; par2[nxt][0]=now;
            adj2[now].push_back(nxt);
        }
    }

    cnt=0; dfs(0, s1, e1, adj1);
    cnt=0; dfs(N-1, s2, e2, adj2);
    for(i=0; i<N; i++) A[s1[i]]=s2[i];
    init(1, 0, N-1);

    for(j=1; j<=20; j++) for(i=0; i<N; i++) par1[i][j]=par1[par1[i][j-1]][j-1];
    for(j=1; j<=20; j++) for(i=0; i<N; i++) par2[i][j]=par2[par2[i][j-1]][j-1];

    for(i=0; i<Q; i++)
    {
        int s=S[i], e=E[i];
        if(S[i]<L[i] || E[i]>R[i]) continue;
        for(j=20; j>=0; j--) if(par1[s][j]>=L[i]) s=par1[s][j];
        for(j=20; j>=0; j--) if(par2[e][j]<=R[i]) e=par2[e][j];
        if(query(1, 0, N-1, s1[s], e1[s], s2[e], e2[e])) ans[i]=1;
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void init(int, int, int)':
werewolf.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int, int)':
werewolf.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~

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