Submission #379243

#	Time	Username	Problem	Language	Result	Execution time	Memory
379243		Sorting	Werewolf (IOI18_werewolf)	C++17	100 / 100	764 ms	101352 KiB

werewolf

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

using namespace std;

const int N = 2e5 + 3;
const int LOGN = 19;

vector<int> adj[N], ans, tr[2][N], tour[2];
vector<array<int, 2>> sweepline[N];
int n, q, s[N], e[N], l[N], r[N];
int st[2][N], en[2][N], par[2][N], lca[LOGN][N], pos[N];

struct DSU{
    int sz[N], p[N], head[N];

    DSU(){}
    void init(){
        for(int i = 0; i < n; ++i)
            sz[i] = 1, p[i] = i, head[i] = i;
    }
    int get_p(int x){
        if(x == p[x]) return x;
        return p[x] = get_p(p[x]);
    }
    bool unite(int a, int b, int idx){
        a = get_p(a), b = get_p(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
        if(!idx) head[a] = max(head[a], head[b]);
        else head[a] = min(head[a], head[b]);
        return true;
    }
} dsu;

struct Fenwick{
    int a[N];
    
    Fenwick(){}
    void update(int i){
        for(++i; i < N; i += i&-i)
            a[i] += 1;
    }
    int query(int i){
        int ans = 0;
        for(++i; i >= 1; i -= i&-i)
            ans += a[i];
        return ans;
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
} f;

void euler_tour(int u, int idx){
    st[idx][u] = tour[idx].size();
    tour[idx].push_back(u);
    for(int to: tr[idx][u])
        euler_tour(to, idx);
    en[idx][u] = tour[idx].size() - 1;
}

void do_lca(int idx){
    for(int i = 0; i < n; ++i)
        lca[0][i] = par[idx][i];
    for(int j = 1; j < LOGN; ++j)
        for(int i = 0; i < n; ++i)
            lca[j][i] = lca[j - 1][lca[j - 1][i]];

    for(int i = 0; i < q; ++i){
        if(idx == 0){
            for(int j = LOGN - 1; j >= 0; --j)
                if(lca[j][e[i]] <= r[i])
                    e[i] = lca[j][e[i]];
        }
        else{
            for(int j = LOGN - 1; j >= 0; --j)
                if(lca[j][s[i]] >= l[i])
                    s[i] = lca[j][s[i]];
        }
    }
}

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, q = _S.size();
    ans.resize(q, 0);
    for(int i = 0; i < _X.size(); ++i){
        adj[_X[i]].push_back(_Y[i]);
        adj[_Y[i]].push_back(_X[i]);
    }
    for(int i = 0; i < q; ++i)
        s[i] = _S[i], e[i] = _E[i], l[i] = _L[i], r[i] = _R[i];

    dsu.init();
    for(int i = 0; i < n; ++i){
        for(int to: adj[i]){
            int x = dsu.head[dsu.get_p(to)];
            if(to < i && dsu.unite(to, i, 0)){
                tr[0][i].push_back(x);
                par[0][x] = i;
                //cout << "edge0 " << i << " -> " << x << endl;
            }
        }
    }
    par[0][n - 1] = n - 1;

    dsu.init();
    for(int i = n - 1; i >= 0; --i){
        for(int to: adj[i]){
            int x = dsu.head[dsu.get_p(to)];
            if(to > i && dsu.unite(to, i, 1)){
                tr[1][i].push_back(x);
                par[1][x] = i;
                //cout << "edge1 " << i << " -> " << x << endl;
            }
        }
    }
    par[1][0] = 0;

    //cout << "done with dsu" << endl;

    euler_tour(n - 1, 0);
    euler_tour(0, 1);

    //cout << "done with euler_tour" << endl;

    do_lca(0);
    do_lca(1);

    for(int i = 0; i < q; ++i){
        //cout << i << " sweepline" << endl;
        sweepline[st[1][s[i]]].push_back({0, i});
        sweepline[en[1][s[i]] + 1].push_back({1, i});
    }

    for(int i = 0; i < n; ++i){
        //cout << " tour " << tour[0][i] << endl;
        pos[tour[0][i]] = i;
    }

    for(int i = 0; i <= n; ++i){
        //cout << i << endl;
        for(auto [type, idx]: sweepline[i]){
            //cout << type << " " << idx << " type idx" << endl;
            if(!type) ans[idx] = f.query(st[0][e[idx]], en[0][e[idx]]);
            else ans[idx] = !!(f.query(st[0][e[idx]], en[0][e[idx]]) - ans[idx]);
        }
        if(i != n) f.update(pos[tour[1][i]]);
    }

    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
/*
2 1 1
0 1
1 0 1 0
*/

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:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < _X.size(); ++i){
      |                    ~~^~~~~~~~~~~

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