제출 #792680

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

werewolf

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

using namespace std;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

typedef long long ll;

const int maxn5 = 5e5 + 10;
const int lg    = 20;

vector <int> ret, adj[maxn5];
vector <pair<int, pair<int, int>>> req[maxn5];
int n;

void gadd(int);
void grem(int);
void gans(int, int, int);

namespace fen{

    int fen[maxn5];

    void add(int id, int val){
        for(; id < maxn5; id += id & -id)
            fen[id] += val;
    }

    int get(int id){
        int ret = 0;
        for(; id; id -= id & -id)
            ret += fen[id];
        return ret;
    }

    int get(int l, int r){
        return get(r) - get(l - 1);
    }
}

struct dsu{

    int lcpar[lg][maxn5], par[maxn5], ti, st[maxn5], ft[maxn5];
    int ver[maxn5], sz[maxn5], newnode, val[maxn5];
    pair <int, int> ed[maxn5];
    bool mark[maxn5];


    dsu(){
        memset(lcpar, -1, sizeof lcpar);
        memset(par, -1, sizeof par);
        memset(mark, false, sizeof mark);
        memset(ed, -1, sizeof ed);
        ti = 2;
    }

    int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}

    void add(int x){
        mark[x] = true;
        for(auto u : adj[x]) if(mark[u]){
            int a = get_par(u), b = get_par(x);
            //////cout << u << ' ' << x << ' ' << a << ' ' << b << endl;
            if(a == b)
                continue;
            //////cout << "ya merging " << a << ' ' << b << ' ' << newnode << endl; 
            par[a] = par[b] = lcpar[0][a] = lcpar[0][b] = newnode;
            ed[newnode] = {a, b};
            val[newnode] = x;
            newnode++;
        }
    }

    void dfs_det(int v){
        sz[v] = 1;
        for(int i = 1; i < lg && lcpar[i - 1][v] != -1; i++)
            lcpar[i][v] = lcpar[i - 1][lcpar[i - 1][v]];
        st[v] = ++ti;
        ver[ti] = v;
        if(ed[v].fi == -1){
            ft[v] = ti;
            return;
        }
        dfs_det(ed[v].fi);
        dfs_det(ed[v].se);
        sz[v] += sz[ed[v].fi] + sz[ed[v].se];
        if(sz[ed[v].fi] < sz[ed[v].se])
            swap(ed[v].fi, ed[v].se);
        ft[v] = ti;
    }

    void query(int id, int l, int r, int s, int e){
        int x = s;
        for(int i = lg - 1; i >= 0; i--) if(lcpar[i][x] != -1 && val[lcpar[i][x]] >= l)
            x = lcpar[i][x];
        //cout << "in quer of " << l << ' ' << r << ' ' << s << ' ' << e << ' ' << x << ' ' << val[x] << ' ' << newnode << endl;
        req[x].pb({id, {r, e}});
    }

    void inc(int id){
        //cout << "right " << st[id] << endl;
        fen::add(st[id], 1);
    }

    void dec(int id){
        fen::add(st[id], -1);
    }

    void answ(int id, int r, int e){
        int x = e;
        for(int i = lg - 1; i >= 0; i--) if(lcpar[i][x] != -1 && val[lcpar[i][x]] <= r)
            x = lcpar[i][x];
        //cout << "answering " << r << ' ' << e << ' ' << x << ' ' << lcpar[0][e] << ' ' << val[lcpar[0][e]] << endl;
        //cout << st[x] << ' ' << ft[x] << endl;
        ret[id] = fen::get(st[x], ft[x]) > 0;
    }

    void gooni(int v, bool keep){
        //cout << "allright " << v << ' ' << lcpar[0][v] << ' ' << keep << ' ' << val[v] << endl;
        if(ed[v].fi == -1){
            gadd(v);
            for(auto [id, p] : req[v])
                gans(id, p.fi, p.se);
            if(!keep)
                grem(v);
            return;
        }
        gooni(ed[v].se, false);
        gooni(ed[v].fi, true);
        gadd(v);
        for(int i = st[ed[v].se]; i <= ft[ed[v].se]; i++)
            gadd(ver[i]);
        for(auto [id, p] : req[v])
            gans(id, p.fi, p.se);
        if(!keep) 
            for(int i = st[v]; i <= ft[v]; i++) 
                grem(ver[i]);
        return;
    }

} dsu0, dsuN;


void gadd(int v){
    if(v >= n)
        return;
    //cout << "adding " << v << endl;
    dsu0.inc(v);
}

void grem(int v){
    if(v >= n)
        return;
    //cout << "removing " << v << endl;
    dsu0.dec(v);
}

void gans(int a, int b, int c){
    //cout << "going to ans query of " << a << ' ' << b << ' ' << c << endl;
    dsu0.answ(a, b, c);
}


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;
    int q = s.size();
    for(int i = 0; i < q; i++){
        ret.pb(0);
    }
    int m = x.size();
    for(int i = 0; i < m; i++){
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    dsu0.newnode = dsuN.newnode = n;
    for(int i = 0; i < n; i++){
        //////cout << "in dsu 0 " << endl;
        dsu0.add(i);
        //////cout << "in dsu N" << endl;
        dsuN.add(n - i - 1);
        dsu0.val[i] = dsuN.val[i] = i;
    }
    dsuN.dfs_det(dsuN.newnode - 1);
    dsu0.dfs_det(dsu0.newnode - 1);
    //////cout << dsu0.lcpar[0][1] << endl;
    for(int i = 0; i < q; i++)
        dsuN.query(i, l[i], r[i], s[i], e[i]);
    dsuN.gooni(dsuN.newnode - 1, true);
    return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In constructor 'dsu::dsu()':
werewolf.cpp:58:33: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   58 |         memset(ed, -1, sizeof ed);
      |                                 ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from werewolf.h:3,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

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