Submission #853629

#	Time	Username	Problem	Language	Result	Execution time	Memory
853629		errw	Werewolf (IOI18_werewolf)	C++14	0 / 100	508 ms	117340 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
int n,m,q,p[200001],node[200001],l[400001],r[400001],par[400001][20],val[400001],id,x[200001],idx,order[200001];
int lx[200001],rx[200001],ly[200001],ry[200001];
vector <int> ke[400001],a,st[800001];
vector <pii> edge;
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
    int w=i;
    i=f(i);
    j=f(j);
    if (i==j)
        return;
    id++;
    val[id]=w;
    ke[id].push_back(node[i]);
    ke[id].push_back(node[j]);
    node[i]=id;
    p[j]=i;
}
void dfs(int u){
    if (u<n){
        l[u]=r[u]=x[u]=idx;
        idx++;
        return;
    }
    l[u]=1e9,r[u]=0;
    for (int v:ke[u]){
        par[v+1][0]=u+1;
        for (int i=1;i<20;i++)
            par[v+1][i]=par[par[v+1][i-1]][i-1];
        dfs(v);
        l[u]=min(l[u],l[v]);
        r[u]=max(r[u],r[v]);
    }
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={x[order[l]]};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    int i=0,j=0;
    while (i<st[node<<1].size()||j<st[node<<1|1].size()){
        if (i>=st[node<<1].size()){
            st[node].push_back(st[node<<1|1][j]);
            j++;
            continue;
        }
        if (j>=st[node<<1|1].size()){
            st[node].push_back(st[node<<1][i]);
            i++;
            continue;
        }
        if (st[node<<1][i]<st[node<<1|1][j]){
            st[node].push_back(st[node<<1][i]);
            i++;
            continue;
        }
        st[node].push_back(st[node<<1|1][j]);
        j++;
        continue;
    }
}
int get(int node, int l, int r, int u, int v, int y){
    if (l>v||r<u||l>r||u>v)
        return 0;
    if (l>=u&&r<=v)
        return upper_bound(st[node].begin(),st[node].end(),y)-st[node].begin();
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v,y)+get(node<<1|1,mid+1,r,u,v,y);
}
bool get(int l, int r, int x, int y){
    return get(1,0,n-1,l,r,y)-get(1,0,n-1,l,r,x-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){
    m=X.size();
    q=S.size();
    a.assign(q,0);
    iota(p,p+n,0);
    iota(node,node+n,0);
    id=n;
    for (int i=0;i<m;i++)
        edge.push_back({min(X[i],Y[i]),max(X[i],Y[i])});
    sort(edge.begin(),edge.end());
    for (int i=m-1;i>=0;i--)
        unite(edge[i].first,edge[i].second);
    dfs(id);
    for (int i=0;i<q;i++){
        int u=S[i]+1;
        for (int j=19;j>=0;j--)
            if (par[u][j]&&val[par[u][j]-1]>=L[i])
                u=par[u][j];
        lx[i]=l[u-1];
        rx[i]=r[u-1];
    }
    for (int i=0;i<n;i++){
        order[x[i]]=i;
        node[i]=p[i]=i;
    }
    for (int i=0;i<=id;i++)
        ke[i].clear();
    id=n;
    idx=0;
    for (int i=0;i<m;i++)
        swap(edge[i].first,edge[i].second);
    sort(edge.begin(),edge.end());
    for (int i=0;i<m;i++)
        unite(edge[i].first,edge[i].second);
    dfs(id);
    for (int i=0;i<q;i++){
        int u=E[i]+1;
        for (int j=19;j>=0;j--)
            if (par[u][j]&&val[par[u][j]-1]<=R[i])
                u=par[u][j];
        ly[i]=l[u-1];
        ry[i]=r[u-1];
    }
    build(1,0,n-1);
    for (int i=0;i<q;i++)
        a[i]=get(lx[i],rx[i],ly[i],ry[i]);
    return a;
}

Compilation message (stderr)

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (i<st[node<<1].size()||j<st[node<<1|1].size()){
      |            ~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:50:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (i<st[node<<1].size()||j<st[node<<1|1].size()){
      |                                  ~^~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (i>=st[node<<1].size()){
      |             ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (j>=st[node<<1|1].size()){
      |             ~^~~~~~~~~~~~~~~~~~~~~~

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