제출 #404562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404562		balbit	늑대인간 (IOI18_werewolf)	C++14	100 / 100	722 ms	96348 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) cout<<__LINE__<<": "<<#__VA_ARGS__<<"- ",_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cout<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cout<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;

int n;
vector<int> g[maxn];
struct dsu{
    int par[maxn], sz[maxn];
//    vector<int> tree[maxn];
    vector<vector<int> > tree;
    int L[maxn], R[maxn];
    vector<int> ord;
    int IT;
    int find(int x) {return x == par[x]? x : par[x] =  find(par[x]); }
//    int findrng(int x, int l, int r) {
//        if (x == par[x] || par[x] > r || par[x] < l) return x;
//        return findrng(x,l,r);
//    }
    void mrg(int a, int b) { // b is the new parent
        a = find(a); b = find(b);
        if (a == b) return;
//        if (sz[a] > sz[b]) swap(a,b);
        par[a]=b; tree[b].pb(a);
//        sz[b] += sz[a];
    }
//    void buildtree(){
//        REP(i,n) {
//            tree[par[i]].pb(i);
//        }
//    }
    bool seen[maxn];
    void dfs(int v) {
        seen[v] = 1;
        ord.pb(v);
        L[v] = R[v] = IT++;
        for (int u : tree[v]) {
            dfs(u);
            R[v] = R[u];
        }
    }
//    void rundfs() {
//        REP(i,n) {
//            if (!seen[i]) dfs(i);
//        }
//    }
    dsu(){
        tree.resize(n);
        REP(i,maxn) par[i] = i, sz[i] = 1;
        IT = 0;
    }
};
vector<int> ret;
vector<int> rbhere[maxn], lbhere[maxn]; // which queries have respective bounds here
int sub1[maxn], sub2[maxn]; // which subtree do you govern?

int seg[maxn];
void MO(int e, int v) {
    for (++e; e<maxn; e+=e&-e) seg[e] += v;
}
int QU(int e) {
    int re=0;
    for (++e; e>0; e-=e&-e) re += seg[e];
    return re;
}

struct qq{
//    int cnt; // count under this
    int l, r, i, dir;
};
vector<qq> go[maxn];

vector<int> check_validity(int _n, vector<int> mx, vector<int> my, vector<int> S, vector<int> E, vector<int> LB, vector<int> RB) {
    n = _n;
//    return {1,0,0};
//    cout<<"yo"<<endl;
//    return {0,0,0};
//    bug("hi");
    REP(i ,SZ(mx)) {
        g[mx[i]].pb(my[i]);
        g[my[i]].pb(mx[i]);
    }
    int q = SZ(S);
    ret.resize(q);
    REP(i,q) {
        rbhere[RB[i]].pb(i);
        lbhere[LB[i]].pb(i);
    }
    dsu LT, RT;
    // build first tree from left
    REP(i, n) {
        for (int v : g[i]) {
            if ( v<i)
                LT.mrg(v, i); // order matters here! i is the new root
        }
        for (int y : rbhere[i]) {
            sub1[y] = LT.find(E[y]);
        }
    }
//    return {};
    LT.dfs(n-1);
    for (int i = n-1; i>=0; --i) {
        for (int v : g[i]) {
            if (v > i)
                RT.mrg(v,i);
        }
        for (int y : lbhere[i]) {
            sub2[y] = RT.find(S[y]);
//            cout<<"tree 2: "<<y<<' '<<S[y]<<' '<<sub2[y]<<endl;
        }
    }
    RT.dfs(0);
//    cout<<"Tree 2: "<<endl;
//    REP(i,n) cout<<RT.ord[i]<<' ';
//    cout<<endl;
//    vector<qq> ev;
    REP(i, q) {

        int lw = LT.L[sub1[i]], rw = LT.R[sub1[i]];
        int qlw = RT.L[sub2[i]], qrw = RT.R[sub2[i]];
        if (lw-1>=0) go[lw-1].pb({qlw, qrw, i, -1});
        go[rw].pb({qlw, qrw, i,  1});
    }
    REP(i, n) {
        int pos = RT.L[LT.ord[i]];
//        cout<<"pos: "<<pos<<' '<<LT.ord[i]<<endl;
        MO(pos, 1);
        for (qq e : go[i]) {
            ret[e.i] += e.dir * (QU(e.r) - QU(e.l-1));
        }
    }
    REP(i, q) {
        ret[i] = min(ret[i], 1);
    }
    return ret;
}

//#undef BALBIT
//signed main(){
//    IOS();
//
//
//}
//#enidf

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