Submission #315950

#	Time	Username	Problem	Language	Result	Execution time	Memory
315950		jhnah917	Werewolf (IOI18_werewolf)	C++14	100 / 100	1703 ms	136580 KiB

werewolf

#ifndef LOCAL
#include "werewolf.h"
#endif

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct UnionFind{
    int par[202020];
    UnionFind(){ iota(par, par+202020, 0); }
    int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
    bool merge(int P, int C){
        P = find(P); C = find(C);
        if(P == C) return false;
        par[C] = P; return true;
    }
} uf;

struct MergeSortTree{
    static const int sz = 1 << 18;
    vector<int> tree[1 << 19];
    void set(int x, int v){
        tree[x|sz].push_back(v);
    }
    void build(){
        for(int i=sz-1; i; i--) merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
    }
    int query(int l, int r, int mn, int mx){
        l |= sz; r |= sz;
        while(l <= r){
            if(l & 1){
                auto it = lower_bound(all(tree[l]), mn);
                if(it != tree[l].end() && *it <= mx) return 1;
                l++;
            }
            if(~r & 1){
                auto it = lower_bound(all(tree[r]), mn);
                if(it != tree[r].end() && *it <= mx) return 1;
                r--;
            }
            l >>= 1; r >>= 1;
        }
        return 0;
    }
} seg;

struct Tree{
    int par[22][202020], in[202020], out[202020], pv;
    vector<int> g[202020];
    UnionFind uf;
    void addEdge(int P, int C){
        if(uf.find(P) == uf.find(C)) return;
        C = uf.find(C);
        par[0][C] = P; g[P].push_back(C);
        uf.merge(P, C);
    }
    void dfs(int v){
        in[v] = ++pv;
        for(auto i : g[v]) dfs(i);
        out[v] = pv;
    }
    void build(int n, int rt){
        dfs(rt); par[0][rt] = rt;
        for(int i=1; i<22; i++) for(int j=1; j<=n; j++) par[i][j] = par[i-1][par[i-1][j]];
    }
} tree1, tree2;

int n, m, q;
vector<int> g[202020];

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 = X.size(); q = L.size();
    for(auto &i : X) i++; for(auto &i : Y) i++; // I love 1-based!
    for(auto &i : S) i++; for(auto &i : E) i++; // I love 1-based!
    for(auto &i : L) i++; for(auto &i : R) i++; // I love 1-based!
    vector<int> ret;
    for(int i=0; i<m; i++){
        int s = X[i], e = Y[i];
        g[s].push_back(e); g[e].push_back(s);
    }
    for(int i=1; i<=n; i++){
        for(auto j : g[i]) if(j < i) tree1.addEdge(i, j);
    }
    for(int i=n; i>=1; i--){
        for(auto j : g[i]) if(i < j) tree2.addEdge(i, j);
    }
    tree1.build(n, n); tree2.build(n, 1);
    
    for(int i=1; i<=n; i++) seg.set(tree1.in[i], tree2.in[i]);
    seg.build();
    
    for(int i=0; i<q; i++){
        int t1 = E[i], t2 = S[i];
        for(int j=21; ~j; j--) if(tree1.par[j][t1] <= R[i]) t1 = tree1.par[j][t1];
        for(int j=21; ~j; j--) if(tree2.par[j][t2] >= L[i]) t2 = tree2.par[j][t2];
        ret.push_back(seg.query(tree1.in[t1], tree1.out[t1], tree2.in[t2], tree2.out[t2]));
    }
    return ret;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M, Q; cin >> N >> M >> Q;
    vector<int> X, Y, S, E, L, R;
    for(int i=0; i<M; i++){
        int a, b; cin >> a >> b;
        X.push_back(a); Y.push_back(b);
    }
    for(int i=0; i<Q; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        S.push_back(a); E.push_back(b);
        L.push_back(c); R.push_back(d);
    }
    auto res = check_validity(N, X, Y, S, E, L, R);
    for(auto i : res) cout << i << "\n";
}
#endif

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:79:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   79 |     for(auto &i : X) i++; for(auto &i : Y) i++; // I love 1-based!
      |     ^~~
werewolf.cpp:79:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |     for(auto &i : X) i++; for(auto &i : Y) i++; // I love 1-based!
      |                           ^~~
werewolf.cpp:80:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |     for(auto &i : S) i++; for(auto &i : E) i++; // I love 1-based!
      |     ^~~
werewolf.cpp:80:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |     for(auto &i : S) i++; for(auto &i : E) i++; // I love 1-based!
      |                           ^~~
werewolf.cpp:81:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   81 |     for(auto &i : L) i++; for(auto &i : R) i++; // I love 1-based!
      |     ^~~
werewolf.cpp:81:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |     for(auto &i : L) i++; for(auto &i : R) i++; // I love 1-based!
      |                           ^~~

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