Submission #119426

#	Time	Username	Problem	Language	Result	Execution time	Memory
119426		onjo0127	Werewolf (IOI18_werewolf)	C++11	100 / 100	1907 ms	159112 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

struct segtree {
    vector<int> T;
    int get(int idx, int s, int e, int l, int r) {
        if(r < s || e < l) return 0;
        if(l <= s && e <= r) return T[idx];
        int m = s+e >> 1;
        return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
    }
    void upd(int idx, int s, int e, int p, int v) {
        if(p < s || e < p) return;
        if(s == e) {
            T[idx] = v;
            return;
        }
        int m = s+e >> 1;
        upd(idx*2, s, m, p, v);
        upd(idx*2+1, m+1, e, p, v);
        T[idx] = T[idx*2] + T[idx*2+1];
    }
    segtree(int sz) { T.resize(4*sz); }
};

struct UF {
    int P[400009], X[400009];
    int root(int x) {
        if(P[x] == x) return x;
        return P[x] = root(P[x]);
    }
    pii merg(int u, int v, int Xi) {
        u = root(u); v = root(v);
        int a = X[u], b = X[v];
        X[v] = X[u] = Xi;
        P[u] = v;
        return (pii){a, b};
    }
    UF(int sz) {
        for(int i=0; i<sz; i++) P[i] = i, X[i] = i;
    }
};

const int FF = 400009;
bool HVS[FF], WVS[FF];
int ans[FF], x[FF], ys[FF], ye[FF], C[FF], lineId[FF];
int Hw[FF], Ww[FF], HP[22][FF], WP[22][FF], l, Hi[FF], Ho[FF], Wi[FF], Wo[FF], Ht = 1, Wt = 1;
vector<int> adj[FF], HT[FF], WT[FF];

void WA() {
    exit(0);
}

void Hdfs(int x, int p) {
    Hi[x] = Ht;
    if((int)HT[x].size() == 0) ++Ht;
    HP[0][x] = p;
    for(auto& it: HT[x]) Hdfs(it, x);
    Ho[x] = Ht - 1;
}

void Wdfs(int x, int p) {
    Wi[x] = Wt;
    if((int)WT[x].size() == 0) ++Wt;
    WP[0][x] = p;
    for(auto& it: WT[x]) Wdfs(it, x);
    Wo[x] = Wt - 1;
}

UF HUF(400001), WUF(400001);

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size(), Q = S.size();
    for(int i=0; i<M; i++) {
        int u = X[i], v = Y[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int I = N - 1;
    for(int i=N-1; i>=0; i--) {
        for(auto& it: adj[i]) {
            if(it < i) continue;
            int u = i, v = it;
            if(HUF.root(u) != HUF.root(v)) {
                int a, b; tie(a, b) = HUF.merg(u, v, ++I);
                HT[I].push_back(a);
                HT[I].push_back(b);
                Hw[I] = i;
            }
        }
    }
    Hdfs(I, I);
    I = N - 1;
    for(int i=0; i<N; i++) {
        for(auto& it: adj[i]) {
            if(it > i) continue;
            int u = i, v = it;
            if(WUF.root(u) != WUF.root(v)) {
                int a, b; tie(a, b) = WUF.merg(u, v, ++I);
                WT[I].push_back(a);
                WT[I].push_back(b);
                Ww[I] = i;
            }
        }
    }
    Wdfs(I, I);
/*
    puts("DFS Ordering");
    for(int i=0; i<N; i++) printf("%d ", Hi[i]);
    puts("");
    for(int i=0; i<N; i++) printf("%d ", Wi[i]);
    puts("\n");
*/
    for(int i=1; (1<<i)<=I; i++) {
        for(int j=0; j<=I; j++) {
            HP[i][j] = HP[i-1][HP[i-1][j]];
            WP[i][j] = WP[i-1][WP[i-1][j]];
        }
        l = i;
    }

    vector<pii> evt;
    for(int i=0; i<N; i++) evt.push_back({1, i});
    int lineIdx = 0;
    for(int i=0; i<Q; i++) {
        int Hnow = S[i], Wnow = E[i];
        for(int j=l; j>=0; j--) if(Hw[HP[j][Hnow]] >= L[i]) Hnow = HP[j][Hnow];
        for(int j=l; j>=0; j--) if(Ww[WP[j][Wnow]] <= R[i]) Wnow = WP[j][Wnow];

        x[++lineIdx] = Hi[Hnow] - 1; C[lineIdx] = -1;
        ys[lineIdx] = Wi[Wnow]; ye[lineIdx] = Wo[Wnow];
        lineId[lineIdx] = i;
        evt.push_back({2, lineIdx});

        x[++lineIdx] = Ho[Hnow]; C[lineIdx] = +1;
        ys[lineIdx] = Wi[Wnow]; ye[lineIdx] = Wo[Wnow];
        lineId[lineIdx] = i;
        evt.push_back({2, lineIdx});

        //printf("rectangle : (%d, %d, %d, %d)\n", Hi[Hnow], Wi[Wnow], Ho[Hnow], Wo[Wnow]);
    }
    sort(evt.begin(), evt.end(), [&](pii A, pii B) {
        int Aty, Aid, Bty, Bid;
        tie(Aty, Aid) = A; tie(Bty, Bid) = B;
        int ax = (Aty == 1 ? Hi[Aid] : x[Aid]), bx = (Bty == 1 ? Hi[Bid] : x[Bid]);
        if(ax == bx) return Aty < Bty;
        return ax < bx;
    });
    segtree seg(N);
    for(auto& it: evt) {
        int ty, id; tie(ty, id) = it;
        if(ty == 1) {
            seg.upd(1, 1, N, Wi[id], 1);
            //printf("dot update: vertex: %d, (%d, %d)\n", id, Hi[id], Wi[id]);
        }
        if(ty == 2) ans[lineId[id]] += C[id] * seg.get(1, 1, N, ys[id], ye[id]);
    }
    vector<int> A(Q, 0);
    for(int i=0; i<Q; i++) if(ans[i]) A[i] = 1;
    return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'int segtree::get(int, int, int, int, int)':
werewolf.cpp:12:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
werewolf.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
werewolf.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~

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