Submission #379303

#	Time	Username	Problem	Language	Result	Execution time	Memory
379303		rocks03	Werewolf (IOI18_werewolf)	C++14	Compilation error	0 ms	0 KiB

werewolf

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class Dsu{
public:
    vector<int> p;
    init(int n){
        p.resize(n);
        iota(all(p), 0);
    }
    int find(int x){
        if(x == p[x]) return x;
        return (p[x] = find(p[x]));
    }
    bool unite(int a, int b){
        a = find(a), b = find(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
};

class MergeSortTree{
public:
    vector<vector<int>> st;
    MergeSortTree(int N, vector<int>& y){
        st.resize(4 * N);
        build(0, 0, N - 1, y);
    }
    void merge(int i){
        int cl = 2 * i + 1, cr = 2 * i + 2;
        for(int x : st[cl]) st[i].pb(x);
        for(int x : st[cr]) st[i].pb(x);
        sort(all(st[i]));
    }
    void build(int i, int l, int r, vector<int>& y){
        if(l == r){
            if(y[l] != -1)
                st[i].pb(y[l]);
        } else{
            int m = (l + r) / 2;
            build(2 * i + 1, l, m, y);
            build(2 * i + 2, m + 1, r, y);
            merge(i);
        }
    }
    int query(int i, int l, int r, int qlx, int qrx, int qly, int qry){
        if(qlx <= l && r <= qrx){
            int p = lower_bound(all(st[i]), qly) - st[i].begin();
            if(p < SZ(st[i]) && qly <= st[i][p] && st[i][p] <= qry){
                return 1;
            }
            return 0;
        }
        if(qrx < l || qlx > r)
            return 0;
        int m = (l + r) / 2;
        int ans1 = query(2 * i + 1, l, m, qlx, qrx, qly, qry);
        int ans2 = query(2 * i + 2, m + 1, r, qlx, qrx, qly, qry);
        return max(ans1, ans2);
    }
};

const int MAXN = 1e6;
int N, M, Q;
vector<int> g[MAXN];
int timer, tin[MAXN], tou[MAXN];

void dfs(int v, int p){
    tin[v] = timer++;
    for(int u : g[v]){
        if(u ^ p){
            dfs(u, v);
        }
    }
    tou[v] = timer - 1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    ::N = N; M = SZ(X), Q = SZ(S);
    int root; Dsu dsu;
    auto add_edge = [&](int u, int v){
        u = dsu.find(u), v = dsu.find(v);
        dsu.unite(root, u);
        g[root].pb(u);
        if(dsu.unite(root, v)){
            g[root].pb(v);
        }
        root++;
    };
    vector<int> edge[N];
    rep(i, 0, M){
        edge[X[i]].pb(Y[i]);
        edge[Y[i]].pb(X[i]);
    }
    vector<int> q[N];
    dsu.init(N + M); root = N;
    rep(i, 0, Q){
        q[L[i]].pb(i);
    }
    vector<int> a(Q);
    per(l, N - 1, 0){
        for(int u : edge[l]){
            if(u >= l)
                add_edge(l, u);
        }
        for(int i : q[l]){
            a[i] = dsu.find(S[i]);
        }
        q[l].clear();
    }
    timer = 0;
    rep(v, 0, N + M){
        if(dsu.find(v) == v){
            dfs(v, -1);
        }
    }
    vector<pii> p1(N + M);
    rep(v, 0, N + M){
        p1[v] = {tin[v], tou[v]};
    }
    rep(i, 0, N + M){
        g[i].clear();
    }
    dsu.init(N + M); root = N;
    rep(i, 0, Q){
        q[R[i]].pb(i);
    }
    vector<int> b(Q);
    rep(r, 0, N){
        for(int u : edge[r]){
            if(u <= r)
                add_edge(r, u);
        }
        for(int i : q[r]){
            b[i] = dsu.find(E[i]);
        }
        q[r].clear();
    }
    timer = 0;
    rep(v, 0, N + M){
        if(dsu.find(v) == v){
            dfs(v, -1);
        }
    }
    vector<pii> p2(N + M);
    rep(v, 0, N + M){
        p2[v] = {tin[v], tou[v]};
    }
    vector<int> y(N + M, -1);
    rep(v, 0, N){
        y[p1[v].ff] = p2[v].ff;
    }
    MergeSortTree mst(N + M, y);
    vector<int> ans(Q);
    rep(i, 0, Q){
        int s = a[i], t = b[i];
        ans[i] = mst.query(0, 0, N + M - 1, p1[s].ff, p1[s].ss, p2[t].ff, p2[t].ss);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp:23:15: error: ISO C++ forbids declaration of 'init' with no type [-fpermissive]
   23 |     init(int n){
      |               ^
werewolf.cpp: In member function 'int Dsu::init(int)':
werewolf.cpp:26:5: warning: no return statement in function returning non-void [-Wreturn-type]
   26 |     }
      |     ^