Submission #116929

#	Time	Username	Problem	Language	Result	Execution time	Memory
116929		pzdba	Werewolf (IOI18_werewolf)	C++14	100 / 100	1390 ms	147592 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
vector<int> g[200005], g2[200005], g3[200005];
int par2[19][200005], par3[19][200005];
int p[200005];
int mapp[200005];
int sz[200005];
int root(int a){
    return p[a] == a?a:(p[a]=root(p[a]));
}
void merge(int a, int b, int t){
    a = root(a), b = root(b);
    if(a != b){
        p[a] = b;
        if(t == 0) sz[b] = min(sz[b], sz[a]);
        else sz[b] = max(sz[b], sz[a]);
    }
}
int arr2[200005], arr3[200005], j = 1;
int s2[200005], e2[200005], s3[200005], e3[200005];
void dfs2(int u, int p){
    arr2[j++] = u;
    par2[0][u] = p;
    s2[u] = j-1;
    for(int i=0;i<g2[u].size();i++){
        int v = g2[u][i];
        dfs2(v, u);
    }
    e2[u] = j-1;
}
void dfs3(int u, int p){
    arr3[j++] = u;
    par3[0][u] = p;
    s3[u] = j-1;
    for(int i=0;i<g3[u].size();i++){
        int v = g3[u][i];
        dfs3(v, u);
    }
    e3[u] = j-1;
}

set<int> dp[200005];
set<int>::iterator its;
vector<pipii> cur[200005];
vector<int> ans;
void dfs(int u, int p){
    dp[u].insert(mapp[u]);
    for(int i=0;i<g3[u].size();i++){
        int v = g3[u][i];
        dfs(v, u);
        if(dp[u].size() < dp[v].size()) swap(dp[u], dp[v]);
        for(its = dp[v].begin();its != dp[v].end();its++) dp[u].insert(*its);
    }
    for(int i=0;i<cur[u].size();i++){
        int j = cur[u][i].first;
        int l = cur[u][i].second.first, r = cur[u][i].second.second;
        its = dp[u].lower_bound(l);
        if(l <= *its && *its <= r) ans[j] = 1;
        else ans[j] = 0;
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
    int n = N;
    int m = X.size();
    int q = S.size();
    ans.resize(q);
    for(int i=0;i<m;i++){
        int a, b;
        a = X[i]+1, b = Y[i]+1;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
    for(int i=n;i>=1;i--){
        for(int j=0;j<g[i].size();j++){
            int v = g[i][j];
            if(v >= i){
                if(root(i) != root(v)){
                    int r = root(v);
                    g2[i].push_back(sz[r]);
                }
                merge(i, v, 0);
            }
        }
    }
    for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++){
            int v = g[i][j];
            if(v <= i){
                if(root(i) != root(v)){
                    int r = root(v);
                    g3[i].push_back(sz[r]);
                }
                merge(i, v, 1);
            }
        }
    }
    j = 1;
    dfs2(1, 0); // human
    j = 1;
    dfs3(n, 0); // wolf

    j--;
    for(int i=1;i<=n;i++){
        mapp[arr2[i]] = i;
    }

    for(int j=1;j<=18;j++){
        for(int i=1;i<=n;i++){
            if(par2[j-1][i] != 0) par2[j][i] = par2[j-1][par2[j-1][i]];
            if(par3[j-1][i] != 0) par3[j][i] = par3[j-1][par3[j-1][i]];
        }
    }
    for(int i=0;i<q;i++){
        int s, e, l, r;
        s = S[i]+1, e = E[i]+1, l = L[i]+1, r = R[i]+1;
        for(int j=18;j>=0;j--){
            if(par2[j][s] != 0 && par2[j][s] >= l) s = par2[j][s];
            if(par3[j][e] != 0 && par3[j][e] <= r) e = par3[j][e];
        }
        int ll = s2[s], rr = e2[s];
        cur[e].push_back(pipii(i, pii(ll, rr)));
    }
    dfs(n, 0);
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g2[u].size();i++){
                 ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs3(int, int)':
werewolf.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g3[u].size();i++){
                 ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g3[u].size();i++){
                 ~^~~~~~~~~~~~~
werewolf.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cur[u].size();i++){
                 ~^~~~~~~~~~~~~~
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:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[i].size();j++){
                     ~^~~~~~~~~~~~
werewolf.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[i].size();j++){
                     ~^~~~~~~~~~~~

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