Submission #706418

#	Time	Username	Problem	Language	Result	Execution time	Memory
706418		lukameladze	Werewolf (IOI18_werewolf)	C++14	100 / 100	736 ms	143244 KiB

werewolf

#include "werewolf.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 4e5 + 5;
int par[N][2],cnt[2],tin[2],in[N][2], out[N][2], tree[4 * N];
vector <int> v[N][2];
int get_col(int a, int ty) {
    if (a == par[a][ty]) return par[a][ty];
    else return par[a][ty] = get_col(par[a][ty],ty);    
}
void merge(int a, int b, int ty) {
    a = get_col(a, ty);
    b = get_col(b, ty);
    if (a == b) return ;
    cnt[ty]++;
    par[a][ty] = cnt[ty]; 
    par[b][ty] = cnt[ty];
    par[cnt[ty]][ty] = cnt[ty]; 
    v[cnt[ty]][ty].pb(a);  
    v[cnt[ty]][ty].pb(b); 
}
void dfs(int a, int p, int ty) {
    tin[ty]++;
    in[a][ty] = tin[ty];
    //cout<<a<<" "<<in[a][ty]<<"\n";
    for (int to : v[a][ty]) {
        if (to == p) continue;
//        cout<<ty<<" --- > "<<a<<" "<<to<<"\n";
        dfs(to, a, ty);
    }
    out[a][ty] = tin[ty];
}
void dfs1(int a, int p, int ty) {
    tin[ty]++;
    in[a][ty] = tin[ty];
//    cout<<a<<" "<<in[a][ty]<<"\n";
    for (int to : v[a][ty]) {
        if (to == p) continue;
        dfs1(to, a, ty);
    }
    out[a][ty] = tin[ty];
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[node] = max(tree[node],val);
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node, le,mid,idx,val);
    update(2 * node + 1, mid + 1, ri, idx,val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return -1;
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) / 2;
    return max(getans(2 * node, le,mid,start, end), getans(2 * node + 1, mid + 1, ri, start, end));
}
vector <int> vec[N],quer[N];
vector <pii> queries[N],add[N];
pii que[N];
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {  
    int q = s.size();
    int m = x.size();
    for (int i = 0; i < m; i++) {
        vec[x[i]].pb(y[i]);
        vec[y[i]].pb(x[i]);
    }
    // First Tree 
    cnt[0] = n - 1; cnt[1] = n - 1;
    for (int i = 0; i < q; i++) {
        queries[l[i]].pb({s[i], i});
    }
    for (int i = 0; i < n; i++) { par[i][0] = i;}
    for (int i = n - 1; i >= 0; i--) {
        for (int to : vec[i]) {
            if (to >= i) {
                merge(to, i, 0);
            }
        }
        for (pii sth : queries[i]) {
            int strt = sth.f; int idx = sth.s;
            que[idx].f = get_col(strt, 0); 
        }
    }
    // Second Tree
    for (int i = 0; i < n; i++) { par[i][1] = i;}
    for (int i = 0; i <= n - 1; i++) {
        queries[i].clear();
    }
    for (int i = 0; i < q; i++) {
        queries[r[i]].pb({e[i], i});
    }
    for (int i = 0; i <= n - 1; i++) {
        for (int to : vec[i]) {
            if (to <= i) {
                merge(to, i, 1); 
            }
        }
        for (pii sth : queries[i]) {
            int strt = sth.f; int idx = sth.s;
            que[idx].s = get_col(strt, 1); 
        }
    }  
    for (int i = 0; i <= cnt[0]; i++) {
        if (get_col(i, 0) == i) {
            v[cnt[0] + 1][0].pb(i);
        }
    }
    dfs(cnt[0] + 1, -1, 0);
    for (int i = 0; i <= cnt[1]; i++) {
        if (get_col(i, 1) == i) {
            v[cnt[1] + 1][1].pb(i);
        }
    }
    dfs1(cnt[1] + 1, -1, 1);
    int mx = 0;
    for (int i = 0; i < q; i++) {
        quer[out[que[i].f][0]].pb(i); 
        mx = max(mx, out[que[i].f][0] + 1);
    }
    for (int i = 0; i < n; i++) {
        add[out[i][0]].pb({in[i][1], in[i][0]});
        mx = max(mx, in[i][1]);
    }
    vector<int> ans(q);
    for (int i = 0; i < 4 * N; i++) tree[i] = -1;
    for (int i = 0; i < mx; i++) {
        for (pii sth : add[i]) {
            update(1,0,mx,sth.f, sth.s);
        }
        for (int id : quer[i]) {
            if (getans(1, 0, mx, in[que[id].s][1], out[que[id].s][1]) >= in[que[id].f][0]) {
                ans[id] = 1;
            } else ans[id] = 0;
        }
    }
    return ans;
}

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