Submission #1145691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145691		Issa	Werewolf (IOI18_werewolf)	C++17	100 / 100	682 ms	142280 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;

int n;
vector<tuple<int, int, int>> g[maxn];
struct asd{
    int t;
    int nxt[maxl][maxn];
    vector<int> g[maxn];
    int p[maxn], a[maxn];
    int tin[maxn], tout[maxn];
    void calc(){
        for(int i = 1; i <= n; i++){
            p[i] = i;
        }
    } int get(int v){
        if(p[v] == v) return v;
        return p[v] = get(p[v]);
    } void join(int a, int b, int c){
        a = get(a), b = get(b);
        if(a == b) return;
        if((a < b) != c) swap(a, b);
        // cout << a << ' ' << b << ' ' << c << ent;
        p[b] = a; g[a].push_back(b);
    } void dfs(int v){
        tin[v] = ++t;
        a[t] = v;
        for(int k = 1; k < maxl; k++){
            nxt[k][v] = nxt[k-1][nxt[k-1][v]];
        }
        for(int to: g[v]){
            nxt[0][to] = v;
            dfs(to);
        } tout[v] = t;
    }
} A, B;

int d[maxn * 4];
void upd(int i, int x, int v = 1, int tl = 1, int tr = n){
    d[v] = max(d[v], x);
    if(tl < tr){
        int mid = (tl + tr) >> 1;
        if(i <= mid) upd(i, x, v<<1, tl, mid);
        else upd(i, x, v<<1|1, mid+1, tr);
    }
} int get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return d[v];
    int mid = (tl + tr) >> 1;
    return max(get(l, r, v<<1, tl, mid)
    , get(l, r, v<<1|1, mid+1, tr));
}

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) {
    n = N;
    vector<pii> e;
    for(int i = 0; i < X.size(); i++){
        e.push_back({X[i] + 1, Y[i] + 1});
    } sort(e.begin(), e.end(), [](pii a, pii b){
        return max(a.first, a.second) <
               max(b.first, b.second);
    }); B.calc();  A.calc();
    for(auto [a, b]: e) B.join(a, b, 0);
    sort(e.begin(), e.end(), [](pii a, pii b){
        return min(a.first, a.second) >
               min(b.first, b.second);
    }); for(auto [a, b]: e) A.join(a, b, 1);
    A.dfs(1); B.dfs(n);
    vector<int> ans(S.size(), 0);
    for(int i = 0; i < S.size(); i++){
        int a = S[i] + 1, b = E[i] + 1;
        L[i]++; R[i]++;
        for(int k = maxl - 1; k >= 0; k--){
            if(A.nxt[k][a] && A.nxt[k][a] >= L[i]){
                a = A.nxt[k][a];
            } if(B.nxt[k][b] && B.nxt[k][b] <= R[i]){
                b = B.nxt[k][b];
            }
        }
        // cout << a << ' ' << A.tin[a] << ' ' << A.tout[a] << ": ";
        // for(int i = A.tin[a]; i <= A.tout[a]; i++){
        //     cout << A.a[i] << ' ';
        // } cout << ent;
        // cout << b << ' ' << B.tin[b] << ' ' << B.tout[b] << ": ";
        // for(int i = B.tin[b]; i <= B.tout[b]; i++){
        //     cout << B.a[i] << ' ';
        // } cout << ent;
        g[A.tout[a]].push_back({a, b, i});
    } for(int i = 1; i <= n; i++){
        upd(B.tin[A.a[i]], i);
        for(auto [a, b, id]: g[i]){
            if(get(B.tin[b], B.tout[b]) >= A.tin[a]){
                ans[id] = 1;
            }
        }
    } return ans;
}

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