Submission #1266275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266275		LmaoLmao	Werewolf (IOI18_werewolf)	C++20	100 / 100	875 ms	172760 KiB

werewolf

#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 8e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

struct KRTTT {
    int p[N];
    int n;
    int w[N]; 
    vector<int> adj[N];
    int get(int u) {
        if(p[u]==u) return u;
        return p[u]=get(p[u]);
    }
    void unite(int u,int v,int wei) {
        u=get(u);
        v=get(v);
        if(u==v) return;
        n++;
        p[u]=p[v]=p[n]=n;
        w[n]=wei;
        adj[n].push_back(u);
        adj[n].push_back(v);
        return;
    }
   int timer=0;
    int up[N][20];
    int eu[N],out[N];
    int rev[N];
    int d[N];
    void dfs(int u) {
        eu[u]=++timer;
        rev[timer]=u;
        for(int i=1;i<20;i++) {
            if(up[u][i-1]==0) continue;
            up[u][i]=up[up[u][i-1]][i-1]; 
        }
        for(int v:adj[u]) {
            //cout << u << ' ' << v << endl;
            d[v]=d[u]+1;
            up[v][0]=u;
            dfs(v);
        }
        out[u]=timer;
    } 
    bool inside(int u,int v) {
        return (u==0) || (eu[u]<=eu[v] && out[v]<=out[u]);
    }
    int lca(int u,int v) {
        if(u==v)return 0;
        //cout << up[u][0] << ' ' << v << endl;
        //cout << __lg(0) << endl;
        for(int i=19;i>=0;i--) {
            if(!inside(up[u][i],v)) {
                u=up[u][i];
            }
        }
        //cout << u << endl;
        return w[up[u][0]];
    }  
    int getu(int u) {
        return rev[u];
    }
} KRT;
struct DSUUU {
    vector<int> c[N];
    set<int> s[N];
    int p[N];
    void unite(int u,int v) {
        u=p[u];
        v=p[v];
        if(u==v) return;
        if(c[u].size()<c[v].size()) swap(u,v);
        for(int x:c[v]) {
            c[u].push_back(x);
            p[x]=u;
        }
        for(int x:s[v]) {
            s[u].insert(x); 
        }
        s[v].clear();
        c[v].clear();
    }
    bool solve(int l,int r,int st,int t) {
        st=p[st];
        //cout << KRT.w[7] << endl; 
        //for(int x:s[st]) cout << x << ' ';
        //cout << endl;
        auto it=s[st].lower_bound(KRT.eu[t]);
        if(it!=s[st].end()) {
            //cout << t << ' ';
            if(KRT.lca(KRT.getu(*it),t)<=r)return 1; 
        }
        if(it!=s[st].begin()) {
            --it; 
            if(KRT.lca(KRT.getu(*it),t)<=r)return 1; 
        } 
        return 0; 
    }
} DSU;
int L[N];
int R[N];
int S[N];
int E[N];

bool cmp(int x,int y) {
    return L[x]>L[y];
}

int qr[N];
aa edge[N];
aa edge1[N];

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> ST, vector<int> ED, vector<int> LE, vector<int> RI) {
    int n=N,m=X.size(),q=ST.size();
    for(int i=1;i<=m;i++) {
        int u=X[i-1],v=Y[i-1];
        edge[i]={max(u,v),u,v};
        edge1[i]={min(u,v),u,v};
    }
    sort(edge+1,edge+1+m);
    for(int i=0;i<n;i++) {
        KRT.p[i]=i;
    }
    KRT.n=n-1;
    for(int i=1;i<=m;i++) {
        KRT.unite(edge[i][1],edge[i][2],edge[i][0]);
    }
    KRT.dfs(KRT.n);
    //cout << 1;
    for(int i=1;i<=q;i++) {
        L[i]=LE[i-1];
        R[i]=RI[i-1];
        S[i]=ST[i-1];
        E[i]=ED[i-1];
        qr[i]=i;
        //cout << S[i] << endl;
    }
    for(int i=0;i<n;i++) {
        DSU.p[i]=i;
        DSU.c[i].push_back(i);
        DSU.s[i].insert(KRT.eu[i]);
    }
    sort(qr+1,qr+q+1,cmp);
    int j=m;
    sort(edge1+1,edge1+1+m);
    vector<int> ans(q,0);
    //for(int x:ans) cout << x << endl;
    for(int i=1;i<=q;i++) {
        while(j>0 && edge1[j][0]>=L[qr[i]]) {
            DSU.unite(edge1[j][1],edge1[j][2]);
            //cout << edge1[j][1] << ' ' << edge1[j][2] << endl;
            j--;
        } 
        //cout << endl;
        ans[qr[i]-1]=DSU.solve(L[qr[i]],R[qr[i]],S[qr[i]],E[qr[i]]);
        //cout << endl;
    }
    return ans;
}

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