Submission #262501

#	Time	Username	Problem	Language	Result	Execution time	Memory
262501		yabsed	Werewolf (IOI18_werewolf)	C++17	100 / 100	1133 ms	126984 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
 
int N, M, Q;
int djs[MAXN];
vector <int> con[MAXN];
 
// 아래에서부터 올라오는 트리 구조
int par[MAXN][18], num[MAXN], out[MAXN];
vector <int> child[MAXN];
 
// 위에서부터 내려가는 트리 구조
int par2[MAXN][18], num2[MAXN], out2[MAXN];
vector <int> child2[MAXN];
 
const int TS = 1<<19, ST = TS/2-1;
vector <int> tree[TS];
 
int find(int n){ return djs[n] == n ? n : (djs[n] = find(djs[n])); }
 
int K = 0;
void dfs(int n)
{
    num[n] = ++K;
    for (int t: child[n]) dfs(t);
    out[n] = K;
}
int K2 = 0;
void dfs2(int n)
{
    num2[n] = ++K2;
    for (int t: child2[n]) dfs2(t);
    out2[n] = K2;
}
 
bool is_exists(int l, int r, int mn, int mx)
{
    for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){
        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--;
        }
    }
    return 0;
}
 
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);
    vector <int> ret(Q, 0);
    for (int i=0;i<M;i++){
        int a = ++X[i], b = ++Y[i];
        con[a].pb(b); con[b].pb(a);
    }
 
    for (int i=1;i<=N;i++) djs[i] = i;
    for (int i=1;i<=N;i++){
        for (int t: con[i]) if (t < i){
            if (find(t) != i){
                int m = find(t); djs[m] = i;
                par[m][0] = i; child[i].pb(m);
            }
        }
    }
    par[N][0] = N;
    for (int i=1;i<18;i++) for (int j=1;j<=N;j++) par[j][i] = par[par[j][i-1]][i-1];
    dfs(N);
 
    for (int i=1;i<=N;i++) djs[i] = i;
    for (int i=N;i;i--){
        for (int t: con[i]) if (t > i){
            if (find(t) != i){
                int m = find(t); djs[m] = i;
                par2[m][0] = i; child2[i].pb(m);
            }
        }
    }
    par2[1][0] = 1;
    for (int i=1;i<18;i++) for (int j=1;j<=N;j++) par2[j][i] = par2[par2[j][i-1]][i-1];
    dfs2(1);
 
    // Merge sort tree
    for (int i=1;i<=N;i++) tree[ST+num[i]].pb(num2[i]);
    for (int i=ST;i;i--){
        const auto &lc = tree[i+i], &rc = tree[i+i+1];
        for (int l=0,r=0;l<sz(lc)||r<sz(rc);){
            if (r == sz(rc) || l < sz(lc) && lc[l] < rc[r]) tree[i].pb(lc[l++]);
            else tree[i].pb(rc[r++]);
        }
    }
 
    for (int i=0;i<Q;i++){
        S[i]++; E[i]++; L[i]++; R[i]++;
        int n = E[i];
        for (int j=18;j--;) if (par[n][j] <= R[i]) n = par[n][j];
        int l = num[n], r = out[n];
 
        n = S[i];
        for (int j=18;j--;) if (par2[n][j] >= L[i]) n = par2[n][j];
        int mn = num2[n], mx = out2[n];
 
        ret[i] = is_exists(l, r, mn, mx);
    }
 
    return ret;
}

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:98:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   98 |             if (r == sz(rc) || l < sz(lc) && lc[l] < rc[r]) tree[i].pb(lc[l++]);

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