oj.uz

Submission #710516

# Submission time Handle Problem Language Result Execution time Memory
710516 2023-03-15T10:01:42 Z rrrr10000 Werewolf (IOI18_werewolf) C++14
100 / 100
 727 ms 84188 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
#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 fi first
#define se second
#define pb emplace_back
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> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}

vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    ll M=X.size(),Q=L.size();
    vvi ord(2);
    vvp rng(2,vp(Q));
    vector<int> ans(Q);
    {
        vvi edge(N),query(N);
        vi par(N,-1),data(N,-1),lca(Q);
        rep(i,M)edge[min(X[i],Y[i])].pb(i);
        rep(i,Q)query[L[i]].pb(i);
        auto root=[&](auto && self, ll i) -> ll {
            if(data[i]==-1)return i;
            data[i]=self(self,data[i]);
            return data[i];
        };
        for(int i=N-1;i>=0;i--){
            for(ll x:edge[i]){
                ll a=root(root,X[x]),b=root(root,Y[x]);
                if(a!=b){
                    if(a<b)swap(a,b);
                    par[a]=data[a]=b;
                }
            }
            for(ll x:query[i]){
                lca[x]=root(root,S[x]);
            }
        }
        vvi ch(N);
        rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
        ll cnt=0;
        vp euler(N);
        auto dfs=[&](auto && self, ll i) -> void {
            ord[0].pb(i);
            euler[i].fi=cnt++;
            for(ll x:ch[i])self(self,x);
            euler[i].se=cnt;
        };dfs(dfs,0);
        rep(i,Q)rng[0][i]=euler[lca[i]];
    }
    {
        vvi edge(N),query(N);
        vi par(N,-1),data(N,-1),lca(Q);
        rep(i,M)edge[max(X[i],Y[i])].pb(i);
        rep(i,Q)query[R[i]].pb(i);
        auto root=[&](auto && self, ll i) -> ll {
            if(data[i]==-1)return i;
            data[i]=self(self,data[i]);
            return data[i];
        };
        rep(i,N){
            for(ll x:edge[i]){
                ll a=root(root,X[x]),b=root(root,Y[x]);
                if(a!=b){
                    if(a>b)swap(a,b);
                    par[a]=data[a]=b;
                }
            }
            for(ll x:query[i]){
                lca[x]=root(root,E[x]);
            }
        }
        vvi ch(N);
        rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
        ll cnt=0;
        vp euler(N);
        auto dfs=[&](auto && self, ll i) -> void {
            ord[1].pb(i);
            euler[i].fi=cnt++;
            for(ll x:ch[i])self(self,x);
            euler[i].se=cnt;
        };dfs(dfs,N-1);
        rep(i,Q)rng[1][i]=euler[lca[i]];
    }
    vvi ins(N);
    rep(i,Q)ins[rng[0][i].fi].pb(i);
    vi rv(N);
    rep(i,N)rv[ord[1][i]]=i;
    vvi seg(N*2);
    rep(i,N){
        for(ll x:ins[i]){
            ll l=rng[1][x].fi,r=rng[1][x].se;
            for(l+=N,r+=N;l<r;l>>=1,r>>=1){
                if(l&1)seg[l++].pb(x);
                if(r&1)seg[--r].pb(x);
            }
        }
        for(ll j=rv[ord[0][i]]+N;j>0;j>>=1){
            for(ll x:seg[j])if(rng[0][x].se>i){
                ans[x]=1;
            }
            seg[j].clear();
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 6 ms 1236 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 5 ms 1236 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct
14 Correct 7 ms 1368 KB Output is correct
15 Correct 6 ms 1492 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 66564 KB Output is correct
2 Correct 578 ms 81832 KB Output is correct
3 Correct 586 ms 81136 KB Output is correct
4 Correct 561 ms 77764 KB Output is correct
5 Correct 543 ms 74624 KB Output is correct
6 Correct 574 ms 65596 KB Output is correct
7 Correct 511 ms 73272 KB Output is correct
8 Correct 576 ms 81712 KB Output is correct
9 Correct 494 ms 77308 KB Output is correct
10 Correct 406 ms 63784 KB Output is correct
11 Correct 448 ms 63288 KB Output is correct
12 Correct 478 ms 65252 KB Output is correct
13 Correct 611 ms 73608 KB Output is correct
14 Correct 609 ms 73668 KB Output is correct
15 Correct 569 ms 74440 KB Output is correct
16 Correct 564 ms 74632 KB Output is correct
17 Correct 482 ms 69060 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 6 ms 1236 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 5 ms 1236 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct
14 Correct 7 ms 1368 KB Output is correct
15 Correct 6 ms 1492 KB Output is correct
16 Correct 583 ms 66564 KB Output is correct
17 Correct 578 ms 81832 KB Output is correct
18 Correct 586 ms 81136 KB Output is correct
19 Correct 561 ms 77764 KB Output is correct
20 Correct 543 ms 74624 KB Output is correct
21 Correct 574 ms 65596 KB Output is correct
22 Correct 511 ms 73272 KB Output is correct
23 Correct 576 ms 81712 KB Output is correct
24 Correct 494 ms 77308 KB Output is correct
25 Correct 406 ms 63784 KB Output is correct
26 Correct 448 ms 63288 KB Output is correct
27 Correct 478 ms 65252 KB Output is correct
28 Correct 611 ms 73608 KB Output is correct
29 Correct 609 ms 73668 KB Output is correct
30 Correct 569 ms 74440 KB Output is correct
31 Correct 564 ms 74632 KB Output is correct
32 Correct 482 ms 69060 KB Output is correct
33 Correct 612 ms 64932 KB Output is correct
34 Correct 291 ms 51448 KB Output is correct
35 Correct 675 ms 67276 KB Output is correct
36 Correct 641 ms 64984 KB Output is correct
37 Correct 629 ms 66564 KB Output is correct
38 Correct 626 ms 65508 KB Output is correct
39 Correct 640 ms 74884 KB Output is correct
40 Correct 622 ms 84188 KB Output is correct
41 Correct 517 ms 66144 KB Output is correct
42 Correct 478 ms 65416 KB Output is correct
43 Correct 727 ms 72252 KB Output is correct
44 Correct 631 ms 66420 KB Output is correct
45 Correct 589 ms 75680 KB Output is correct
46 Correct 622 ms 76052 KB Output is correct
47 Correct 619 ms 75244 KB Output is correct
48 Correct 607 ms 73432 KB Output is correct
49 Correct 596 ms 74704 KB Output is correct
50 Correct 599 ms 74500 KB Output is correct
51 Correct 568 ms 83468 KB Output is correct
52 Correct 572 ms 83548 KB Output is correct