Submission #1225430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225430		lamlamlam	Werewolf (IOI18_werewolf)	C++20	100 / 100	374 ms	100520 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define task "sus"
const int MN = 2e5+5,LG = 19;
int n,m,q,fw[MN];
vector<int> adj[MN];
struct query
{
    int l,r,sign,id;
};
vector<query> ev[MN];
void upd(int u,int val)
{
    for(int x=u; x<MN; x+=x&(-x)) fw[x] += val;
}
int get(int u)
{
    int res = 0;
    for(int x=u; x; x-=x&(-x)) res += fw[x];
    return res;
}
struct KRT
{
    int pa[MN][LG],dsu[MN],h[MN],time_dfs,in[MN],out[MN],et[MN];
    vector<int> g[MN];
    void init()
    {
        for(int i=0; i<=n; i++) {
            for(int j=0; j<LG; j++) pa[i][j] = 0;
            dsu[i] = i;
            h[i] = 0;
        }
    }
    int papa(int x)
    {
        if(x==dsu[x]) return x;
        return dsu[x] = papa(dsu[x]);
    }
    void uni_set(int x,int y)
    {
        int p = papa(y);
        dsu[p] = x;
        g[x+1].push_back(p+1);
    }
    void dfs(int x,int p)
    {
        in[x] = ++time_dfs;
        et[time_dfs] = x;
        pa[x][0] = p;
        h[x] = h[p] + 1;
        for(int i=1; i<LG; i++) pa[x][i] = pa[pa[x][i-1]][i-1];
        for(auto v:g[x]) dfs(v,x);
        out[x] = time_dfs;
    }
}a,b;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    n = N; m = X.size(), q = S.size();
    a.init(); b.init();
    for(int i=0; i<m; i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<n; i++){
        for(auto j:adj[i]){
            if(j>i or a.papa(j)==i) continue;
            a.uni_set(i,j);
        }
    }
    for(int i=n-1; i>=0; i--){
        for(auto j:adj[i]){
            if(j<i or b.papa(j)==i) continue;
            b.uni_set(i,j);
        }
    }
    a.dfs(n,0); b.dfs(1,0);
    //cerr << "TOUR A: "; for(int i=1; i<=n; i++) cerr << a.et[i] << ' '; cerr << endl;
    //cerr << "TOUR B: "; for(int i=1; i<=n; i++) cerr << b.et[i] << ' '; cerr << endl;
    vector<int> ans;
    ans.resize(q,0);
    for(int t=0; t<q; t++){
        int s,e,l,r;
        s = S[t]+1, e = E[t]+1, l = L[t]+1, r = R[t]+1;
        //cerr << "PRE: " << s << ' ' << e << ' ' << l << ' ' << r << endl;
        for(int i=LG-1; i>=0; i--){
            //cerr << "LG: " << i << ' ' << s << ' ' << e << endl;
            if(b.pa[s][i]>=l) s = b.pa[s][i];
            if(a.pa[e][i]<=r and a.pa[e][i]!=0) e = a.pa[e][i];
        }
        //cerr << "POST: " << s << ' ' << e << ' ' << l << ' ' << r << endl;
        ev[max(b.in[s]-1,0)].push_back({a.in[e],a.out[e],-1,t});
        ev[b.out[s]].push_back({a.in[e],a.out[e],1,t});
    }
    for(int i=1; i<=n; i++){
        int u = b.et[i];
        upd(a.in[u],1);
        for(auto q:ev[i]){
            int res = get(q.r) - get(q.l-1);
            ans[q.id] += res * q.sign;
        }
    }
    for(int i=0; i<q; i++) ans[i] = (ans[i]>0);
    return ans;
}

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