Submission #163120

#	Time	Username	Problem	Language	Result	Execution time	Memory
163120		mhy908	Werewolf (IOI18_werewolf)	C++14	100 / 100	966 ms	64420 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
const LL llinf=987654321987654321;
const int inf=987654321;
int n, q;
struct query{
    int l, r;
    int s, e;
    int stx, finx, sty, finy;
    int num;
}qu[200010];
bool operator < (const query &a, const query &b){
    if(a.l!=b.l)return a.l<b.l;
    if(a.r!=b.r)return a.r<b.r;
    if(a.s!=b.s)return a.s<b.s;
    if(a.e!=b.e)return a.e<b.e;
}
bool cmp1(query a, query b){
    if(a.l!=b.l)return a.l<b.l;
    return a<b;
}
bool cmp2(query a, query b){
    if(a.r!=b.r)return a.r>b.r;
    return !(a<b);
}
bool cmp3(query a, query b){
    if(a.finx!=b.finx)return a.finx<b.finx;
    return a<b;
}
vi link[200010];
struct Union_Find{
    int par[200010];
    void init(){for(int i=1; i<=200000; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a);
        b=findpar(b);
        par[a]=b;
    }
    bool chk(int a, int b){return findpar(a)==findpar(b);}
}tl;
struct Treenode{
    int maxx, et;
    int fr, re;
    int l, r;
}treel[400010], treer[400010];
int treelrev[200010], treerrev[200010];
int lrv[200010], rrv[200010];
int point[200010];
int tmp;
void eulerl(int num){
    if(treel[num].l==-1){
        ++tmp;
        treel[num].fr=tmp;
        treel[num].re=tmp;
        treel[num].et=tmp;
        treelrev[treel[num].maxx]=tmp;
        lrv[treel[num].maxx]=num;
        return;
    }
    eulerl(treel[num].l);
    eulerl(treel[num].r);
    treel[num].fr=treel[treel[num].l].fr;
    treel[num].re=treel[treel[num].r].re;
}
void eulerr(int num){
    if(treer[num].l==-1){
        ++tmp;
        treer[num].fr=tmp;
        treer[num].re=tmp;
        treer[num].et=tmp;
        treerrev[treer[num].maxx]=tmp;
        rrv[treer[num].maxx]=num;
        return;
    }
    eulerr(treer[num].l);
    eulerr(treer[num].r);
    treer[num].fr=treer[treer[num].l].fr;
    treer[num].re=treer[treer[num].r].re;
}
void makeltree(){
    sort(qu+1, qu+q+1, cmp1);
    int x=0;
    tl.init();
    for(int i=1; i<=n; i++){
        x++;
        treel[x].maxx=i;
        treel[x].l=-1;
        treel[x].r=-1;
        lrv[i]=x;
        for(int j=0; j<link[i].size(); j++){
            if(link[i][j]>i||tl.chk(i, link[i][j]))continue;
            int temp=tl.findpar(link[i][j]);
            x++;
            treel[x].maxx=i;
            treel[x].l=lrv[temp];
            treel[x].r=x-1;
            lrv[i]=x;
            tl.mergepar(temp, i);
        }
    }
    eulerl(x);
    x=0;
    tl.init();
    int pv=1;
    for(int i=1; i<=n; i++){
        x++;
        for(int j=0; j<link[i].size(); j++){
            if(link[i][j]>i||tl.chk(i, link[i][j]))continue;
            lrv[i]=++x;
            tl.mergepar(link[i][j], i);
        }
        for(; pv<=q; pv++){
            if(qu[pv].l>i)break;
            int t=lrv[tl.findpar(qu[pv].s)];
            qu[pv].stx=treel[t].fr;
            qu[pv].finx=treel[t].re;
        }
    }
}
void makertree(){
    sort(qu+1, qu+q+1, cmp2);
    int x=0;
    tl.init();
    for(int i=n; i>=1; i--){
        x++;
        treer[x].maxx=i;
        treer[x].l=-1;
        treer[x].r=-1;
        rrv[i]=x;
        for(int j=0; j<link[i].size(); j++){
            if(link[i][j]<i||tl.chk(i, link[i][j]))continue;
            int temp=tl.findpar(link[i][j]);
            x++;
            treer[x].maxx=i;
            treer[x].r=rrv[temp];
            treer[x].l=x-1;
            rrv[i]=x;
            tl.mergepar(temp, i);
        }
    }
    tmp=0;
    eulerr(x);
    x=0;
    tl.init();
    int pv=1;
    for(int i=n; i>=1; i--){
        x++;
        for(int j=0; j<link[i].size(); j++){
            if(link[i][j]<i||tl.chk(i, link[i][j]))continue;
            rrv[i]=++x;
            tl.mergepar(link[i][j], i);
        }
        for(; pv<=q; pv++){
            if(qu[pv].r<i)break;
            int t=rrv[tl.findpar(qu[pv].e)];
            qu[pv].sty=treer[t].fr;
            qu[pv].finy=treer[t].re;
        }
    }
}
struct SEGMENT_TREE {
    struct NODE {
        int st, fin;
        int q;
    }tree[800010];
    int x;
    const int inf=987654321;
    int f(int a, int b){return max(a, b);}
    void maketree(int point, int num) {
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        maketree(point*2, num-num/2);
        maketree(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    int query(int a, int b, int point) {
        if(tree[point].st>=a&&tree[point].fin<=b)
            return tree[point].q;
        if(tree[point].st>b||tree[point].fin<a)
            return 0;
        return f(query(a, b, point*2), query(a, b, point*2+1));
    }
    void updaterange(int point, int num, int p) {
        if(tree[point].st==tree[point].fin) {
            tree[point].q=p;
            return;
        }
        if(num<=tree[point*2].fin)updaterange(point*2, num, p);
        else updaterange(point*2+1, num, p);
        tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
    }
    void init(int n) {
        maketree(1, n);
    }
    int get_query(int a, int b) {
        return query(a, b, 1);
    }
    void update(int a, int num) {
        updaterange(1, a, num);
    }
}seg;
vi check_validity(int N, vi X, vi Y, vi E, vi S, vi R, vi L){
    n=N;
    q=S.size();
    for(int i=0; i<q; i++){
        qu[i+1].l=L[i]+1;
        qu[i+1].r=R[i]+1;
        qu[i+1].s=S[i]+1;
        qu[i+1].e=E[i]+1;
        qu[i+1].num=i;
    }
    for(int i=0; i<X.size(); i++){
        link[X[i]+1].pb(Y[i]+1);
        link[Y[i]+1].pb(X[i]+1);
    }
    makeltree();
    makertree();
    for(int i=1; i<=n; i++){
        point[treelrev[i]]=treerrev[i];
    }
    sort(qu+1, qu+q+1, cmp3);
    seg.init(n);
    vi ans(q);
    int pv=1;
    for(int i=1; i<=n; i++){
        seg.update(point[i], i);
        for(; pv<=q; pv++){
            if(i<qu[pv].finx)break;
            int t=seg.get_query(qu[pv].sty, qu[pv].finy);
            if(t>=qu[pv].stx)ans[qu[pv].num]=1;
        }
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void makeltree()':
werewolf.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<link[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
werewolf.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<link[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void makertree()':
werewolf.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<link[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
werewolf.cpp:159:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<link[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:224:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<X.size(); i++){
                  ~^~~~~~~~~
werewolf.cpp: In function 'bool operator<(const query&, const query&)':
werewolf.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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