제출 #1286964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286964		mariaclara	늑대인간 (IOI18_werewolf)	C++17	100 / 100	409 ms	70564 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first 
#define sc second

vi pai, euler, tin, tout;
vector<vi> lift, edges;

int find(int x) {
    if(pai[x] == x) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    pai[x] = y;
    edges[y].pb(x);
}

void dfs(int x) {
    euler.pb(x);
    tin[x] = sz(euler) - 1;

    for(auto viz : edges[x]) 
        lift[0][viz] = x, dfs(viz);

    tout[x] = sz(euler) - 1;
}

void construct_graph(int N, vector<pii> ord) {
    pai.resize(N);
    edges.clear();
    edges.resize(N);

    for(int i = 0; i < N; i++)  pai[i] = i;

    for(auto [a,b] : ord) join(b, a); // a <- b

    euler.clear();
    tin.resize(N);
    tout.resize(N);
    lift.resize(20, vi(N+1));

    lift[0][ord.back().fr] = lift[0][N] = N;
    dfs(ord.back().fr);

    for(int b = 1; b < 20; b++)
        for(int i = 0; i <= N; i++)
            lift[b][i] = lift[b-1][lift[b-1][i]];
}

vi l, r, a, b; // ind, l, r, a, b
vi seg;

void update(int node, int ll, int rr, int val, int pos) {
    seg[node] = max(seg[node], val);

    if(ll == rr) return;

    int mid = (ll+rr)/2;
    if(pos <= mid) update(2*node, ll, mid, val, pos);
    else update(2*node+1, mid+1, rr, val, pos);
}

int query(int node, int ll, int rr, int p, int q) {
    if(rr < p or q < ll) return -1;
    if(p <= ll and rr <= q) return seg[node];

    int mid = (ll+rr)/2;
    return max(query(2*node, ll, mid, p, q), query(2*node+1, mid+1, rr, p, q));
}

vi solve(vi V) {
    int N = sz(V), Q = sz(l);

    vi ans(Q), pos(N);
    vector<vi> qq(N);

    seg.resize(4*N, -1);

    for(int i = 0; i < N; i++) pos[V[i]] = i;

    for(int i = 0; i < Q; i++)
        qq[b[i]].pb(i);

    for(int i = 0; i < N; i++) {
        update(1, 0, N-1, i, pos[i]);

        for(auto it : qq[i]) 
            if(query(1, 0, N-1, l[it], r[it]) >= a[it]) ans[it] = 1;
    }

    return ans;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = sz(X), Q = sz(S);
    vector<pii> ord;

    l.resize(Q);
    r.resize(Q);
    a.resize(Q);
    b.resize(Q);

    // primeiro grafo
    for(int i = 0; i < M; i++) ord.pb({min(X[i], Y[i]), max(X[i], Y[i])});

    sort(all(ord));
    reverse(all(ord));

    construct_graph(N, ord);
    vi V = euler;

    for(int i = 0; i < Q; i++) {
        for(int b = 19; b >= 0; b--)
            if(lift[b][S[i]] >= L[i] and lift[b][S[i]] != N)
                S[i] = lift[b][S[i]];

        l[i] = tin[S[i]];
        r[i] = tout[S[i]];
    }

    // segundo grafo
    for(int i = 0; i < M; i++) swap(ord[i].fr, ord[i].sc);

    sort(all(ord));

    construct_graph(N, ord);
    vi C(N);

    for(int i = 0; i < N; i++) C[euler[i]] = i;

    for(int i = 0; i < Q; i++) {
        for(int b = 19; b >= 0; b--)
            if(lift[b][E[i]] <= R[i]) E[i] = lift[b][E[i]];
        
        a[i] = tin[E[i]];
        b[i] = tout[E[i]];
    }

    // construir vetor e resolver o novo problema
    for(int i = 0; i < N; i++) V[i] = C[V[i]];

    return solve(V);
}

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