Submission #293305

#	Time	Username	Problem	Language	Result	Execution time	Memory
293305		Atill83	Werewolf (IOI18_werewolf)	C++14	0 / 100	760 ms	68540 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = (int) 5e5 + 5;
int n;
int t[MAXN];

void upd(int v, int val){
    v++;
    for(; v < MAXN; v += (v&-v)) 
        t[v] += val;
}

int gt(int l, int r){
    r++;
    int res = 0;
    for(; r; r -= (r&-r)) res += t[r];
    for(; l; l -= (l&-l)) res -= t[l];
    return res;
}


vector<pair<int, int>> Qs[MAXN];


vector<int> A;
struct ali{
    int cev[MAXN], tin[MAXN], tout[MAXN], sz[MAXN];
    int cur = 1;
    int par[MAXN];
    vector<int> adj[MAXN];
    void ini(){
        for(int i = 0; i < n; i++){
            adj[i].clear();
            sz[i] = 1;
            par[i] = i;
        }
    }

    int find_set(int v){
        if(par[v] == v) return v;
        return par[v] = find_set(par[v]);
    }

    void merge(int a, int b, bool cur){
        a = find_set(a);
        b = find_set(b);
        if(a == b) return;
        if(cur){
            if(a < b){ 
                swap(a, b);
            }
            sz[a] += sz[b];
            par[b] = a;
            adj[a].push_back(b);
        }else{
            if(a > b) swap(a, b);
            sz[a] += sz[b];
            par[b] = a;
            adj[a].push_back(b);
        }
    }

    void dfs(int v){
        tin[v] = cur++;
        cev[cur - 1] = v;
        for(int j: adj[v])
            dfs(j);
        
        tout[v] = cur - 1;
    }

    void dfs2(int v, bool keep, ali &s){
        int hv = -1;
        for(int j: adj[v]){
            if(hv == -1 || sz[j] > sz[hv]) 
                hv = j;
        }

        for(int j: adj[v]){
            if(j != hv) 
                dfs2(j, 0, s);
        }

        if(hv != -1)
            dfs2(hv, 1, s);

        for(int j: adj[v]){
            if(j != hv){
                for(int i = tin[j]; i <= tout[j]; i++){
                    upd(s.tin[cev[i]], 1);
                }
            }
        }

        upd(s.tin[v], 1);
        for(auto j: Qs[v]){
            int rs = gt(s.tin[j.first], s.tout[j.first]);
            assert(rs >= 0);
            A[j.second] = (rs > 0);
        }

        if(keep == 0)
            for(int i = tin[v]; i <= tout[v]; i++)
                upd(s.tin[cev[i]], -1);
    }

} st1, st2;






vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    n = N;
    int M = X.size(), Q = S.size();
    st1.ini(); 
    st2.ini();
    A.resize(Q);
    vector<int> esi;
    for(int i = 0; i < M; i++){
        esi.push_back(i);
    }

    sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
        if(min(X[a], Y[a]) == min(X[b], Y[b])){
            return max(X[a], Y[a]) < max(X[b], Y[b]);
        }
        return min(X[a], Y[a]) > min(X[b], Y[b]);
    });
    st1.ini(); st2.ini();
    for(int i = 0; i < M; i++){
        st1.merge(X[esi[i]], Y[esi[i]], 0);
    }

    sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
        if(max(X[a], Y[a]) == max(X[b], Y[b]))
            return min(X[a], Y[a]) > min(X[b], Y[b]);
        return max(X[a], Y[a]) < max(X[b], Y[b]);
    });

    for(int i = 0; i < M; i++){
        st2.merge(X[esi[i]], Y[esi[i]], 1);
    }
    st1.dfs(0);
    st2.dfs(n - 1);
    for(int i = 0; i < Q; i++){
        if(st1.tin[S[i]] < st1.tin[L[i]] || st1.tin[S[i]] > st1.tout[L[i]]){
            L[i] = S[i];
        }

        if(st2.tin[E[i]] < st2.tin[R[i]] || st2.tin[E[i]] > st2.tout[R[i]]){
            R[i] = E[i];
        }
        Qs[L[i]].push_back({R[i], i});
    }



    st1.dfs2(0, 0, st2);
    return A;
}

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