oj.uz

답안 #608467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
608467 2022-07-27T07:48:28 Z rrrr10000 늑대인간 (IOI18_werewolf) C++14
0 / 100
 909 ms 147628 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;

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();
    vvi g(n);
    rep(i,X.size()){
        g[X[i]].pb(Y[i]);g[Y[i]].pb(X[i]);
    }
    vi parL(n,-1),parR(n,-1);
    vvi queryL(n),queryR(n);
    {
        vi pp(n,-1);
        function<ll(ll)> root=[&](ll i){
            if(pp[i]==-1)return i;
            pp[i]=root(pp[i]);
            return pp[i];
        };
        vvi tmp(n);
        rep(i,Q)tmp[L[i]].pb(i);
        for(int i=n-1;i>=0;i--){
            for(auto x:g[i])if(x>i){
                ll t=root(x);
                if(t!=i)parL[t]=pp[t]=i;
            }
            for(ll x:tmp[i])queryL[root(S[x])].pb(x);
        }
    }
    {
        vi pp(n,-1);
        function<ll(ll)> root=[&](ll i){
            if(pp[i]==-1)return i;
            pp[i]=root(pp[i]);
            return pp[i];
        };
        vvi tmp(n);
        rep(i,Q)tmp[R[i]].pb(i);
        rep(i,n){
            for(auto x:g[i])if(x<i){
                ll t=root(x);
                if(t!=i)parR[t]=pp[t]=i;
            }
            for(ll x:tmp[i])queryR[root(E[x])].pb(x);
        }
    }
    vvi gL(n),gR(n);
    rep(i,n)if(parL[i]!=-1)gL[parL[i]].pb(i);
    rep(i,n)if(parR[i]!=-1)gR[parR[i]].pb(i);
    ll cnt=0;
    vp euler(n);
    function<void(ll)> dfs0=[&](ll i){
        euler[i].fi=cnt++;
        for(ll x:gR[i])dfs0(x);
        euler[i].se=cnt;
    };dfs0(n-1);
    vp rng(Q);
    rep(i,n)for(auto x:queryR[i])rng[x]=euler[i];
    vector<set<ll>> dp(n);
    vector<int> ans(Q);
    // for(auto x:rng)cout<<x.fi<<' '<<x.se<<endl;
    // for(auto x:euler)cout<<x.fi<<' '<<x.se<<endl;
    function<void(ll)> dfs1=[&](ll i){
        dp[i].insert(euler[i].fi);
        for(ll x:gL[i]){
            dfs1(x);
            if(dp[i].size()<dp[x].size())swap(dp[i],dp[x]);
            for(ll y:dp[x])dp[i].insert(y);
        }
        for(auto x:queryL[i]){
            auto itr=dp[i].lower_bound(rng[x].fi);
            if(itr!=dp[i].end()&&*itr<=rng[x].se)ans[x]=1;
        }
    };dfs1(0);
    return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 909 ms 147628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -