Submission #123371

#	Time	Username	Problem	Language	Result	Execution time	Memory
123371		neki	Werewolf (IOI18_werewolf)	C++14	15 / 100	4038 ms	299012 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define maxn 200010
#define loop(i, a, b) for(int i=a;i<b;i++)
#define cc(a) cout<< a << endl;
 
 
using namespace std;
 
struct seg{
    map<int, map<int, bool>> tree;
    void update(int x, int y){
        x+=maxn;y+=maxn;
        tree[x][y]=1;
        for(int tx=x;tx>=1;tx>>=1){
            for(int ty=y;ty>=1;ty>>=1) tree[tx][ty]=1;
        }
    }
    bool query(int lx, int ly, int rx, int ry){
        bool ret=0;
        lx+=maxn;ly+=maxn;rx+=maxn;ry+=maxn;
        int slx=lx; int srx=rx;
        for(;slx<srx;slx>>=1, srx>>=1){
            if(slx&1){
                int sly=ly; int sry=ry;
                for(;sly<sry;sly>>=1, sry>>=1){
                    if(sly&1) ret=ret or tree[slx][sly++];
                    if(sry&1) ret=ret or tree[slx][--sry];
                }
                slx++;
            }
            if(srx&1){
                --srx;
                int sly=ly; int sry=ry;
                for(;sly<sry;sly>>=1, sry>>=1){
                    if(sly&1) ret=ret or tree[srx][sly++];
                    if(sry&1) ret=ret or tree[srx][--sry];
                }
            }
        }
        return ret;
    }
};
 
vector<int> edges[maxn];
int pU[maxn];int pV[maxn];
vector<int> cU[maxn];vector<int> cV[maxn];
 
int fndU(int u){return (u==pU[u]) ? u:fndU(pU[u]);}
int fndV(int u){return (u==pV[u]) ? u:fndV(pV[u]);}
 
int sU[maxn];int eU[maxn];int sV[maxn];int eV[maxn];
int cntU=0;int cntV=0;
void dfsU(int u){
    sU[u]=cntU;cntU++;
    for(auto&& v:cU[u]) dfsU(v);
    eU[u]=cntU;cntU++;
}
void dfsV(int u){
    sV[u]=cntV;cntV++;
    for(auto&& v:cV[u]) dfsV(v);
    eV[u]=cntV;cntV++;
}
 
seg r;
 
int faU(int u, int m){
    if (u==pU[u] or pU[u]>m) return u;
    return faU(pU[u], m);
}
int faV(int u, int m){
    if (u==pV[u] or pV[u]<m) return u;
    return faV(pV[u], m);
}
 
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
    int M=X.size();int Q=S.size();
    loop(i, 0, M){edges[X[i]].push_back(Y[i]);edges[Y[i]].push_back(X[i]);}
    loop(i, 0, N) pU[i]=i;loop(i, 0, N) pV[i]=i;
    loop(i, 0, N){
        for(auto&& j: edges[i]){
            if(j>i) continue;
            int pj=fndU(j);
            if(pj==i) continue;
            pU[pj]=i;cU[i].push_back(pj);
        }
    }//disjoint union U
    for(int i=N-1;i>=0;i--){
        for(auto&& j: edges[i]){
            if(j<i) continue;
            int pj=fndV(j);
            if(pj==i) continue;
            pV[pj]=i;cV[i].push_back(pj);
        }
    }//disjoint union V
    dfsU(N-1);dfsV(0);
    loop(i, 0, N) r.update(sU[i], sV[i]);
    vector<int> ans;ans.resize(Q);
    loop(i, 0, Q){
        int na=faV(S[i], L[i]);int nb=faU(E[i], R[i]);
        ans[i]=r.query(sU[nb], sV[na], eU[nb], eV[na]);
    }
    return ans;
}

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