oj.uz

Submission #585928

# Submission time Handle Problem Language Result Execution time Memory
585928 2022-06-29T14:48:15 Z Koosha_mv Werewolf (IOI18_werewolf) C++14
100 / 100
 721 ms 136272 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=4e5+99;

int n,m,Time,par[N],pos[N],A[N],B[N],mark[N],st[2][N],ft[2][N],L[2][N],R[2][N];
pair<int,int> seg[N<<1];
vector<int> ans,ad[N],dl[N],adj[N],g[2][N];
vector<pair<int,int>> vec[2][N];

int getpar(int u){
  if(par[u]<0) return u;
  return par[u]=getpar(par[u]);
}
void merge(int u,int v,int s){
  u=getpar(u),v=getpar(v);
  if(u==v) return ;
  if(s^(u<v)) swap(u,v);
  par[u]+=par[v];
  par[v]=u;
}
void dfs(int u,int s){
  st[s][u]=Time++;
  for(auto v : g[s][u]){
    dfs(v,s);
  }
  ft[s][u]=Time;
}
void upd(int x,pair<int,int> val){
  seg[x+m]=val;
  for(x+=m;x>1;x>>=1){
    seg[x>>1]=max(seg[x],seg[x^1]);
  }
}
pair<int,int> get(int l,int r){
  pair<int,int> ans=mp(-1,0);
  for(l+=m,r+=m;l<r;l>>=1,r>>=1){
    if(l&1){
      maxm(ans,seg[l++]);
    }
    if(r&1){
      maxm(ans,seg[--r]);
    }
  }
  return ans;
}
vector<int> check_validity(int _n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> C,vector<int> D){
  f(i,0,N<<1) seg[i].F=-1;
  n=_n,m=S.size();
  f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
  fill(par,par+N,-1);
  f(i,0,m){
    ans.pb(0);
    swap(S[i],E[i]);
    L[0][i]=R[0][i]=L[1][i]=R[1][i]=n;
    vec[0][D[i]].pb({S[i],i});
    vec[1][C[i]].pb({E[i],i});
  }
  f(u,0,n){
    for(auto v : adj[u]){
      v=getpar(v);
      if(v<u){
        //cout<<u<<" -> "<<v<<endl;
        merge(u,v,0);
        g[0][u].pb(v);
      }
    }
    for(auto p : vec[0][u]){
      A[p.S]=getpar(p.F);
    }
  }
  fill(par,par+N,-1);
  f_(u,n-1,0){
    for(auto v : adj[u]){
      v=getpar(v);
      if(v>u){
        merge(u,v,1);
        g[1][u].pb(v);
      }
    }
    for(auto p : vec[1][u]){
      B[p.S]=getpar(p.F);
    }
  }
  dfs(n-1,0);
  Time=0,dfs(0,1);
  f(i,0,m){
    L[0][i]=st[0][A[i]];
    R[0][i]=ft[0][A[i]];
    L[1][i]=st[1][B[i]];
    R[1][i]=ft[1][B[i]];
  }
  f(i,0,n) A[st[0][i]]=i,B[st[1][i]]=i;
  /*dbga(A,0,n);
  dbga(B,0,n);
  f(i,0,t){
    cout<<L[0][i]<<" "<<R[0][i]<<endl;
    cout<<L[1][i]<<" "<<R[1][i]<<endl;
    cout<<endl;
  }*/
  vector<int> p(m);
  iota(all(p),0);
  sort(all(p),[&](int u,int v){ return L[1][u]<L[1][v]; });
  f(i,0,m) pos[p[i]]=i;
  f(i,0,m){
    ad[L[0][i]].pb(i);
    dl[R[0][i]].pb(i);
  }
  f(i,0,n){
    for(auto id : ad[i]) upd(pos[id],mp(R[1][id],id));
    for(auto id : dl[i]) upd(pos[id],mp(-1,id));
    int x=st[1][A[i]];
    //cout<<A[i]<<" -> "<<st[1][A[i]]<<endl;
    int l=-1,r=m,mid;
    while(l+1<r){
      int mid=(l+r)>>1;
      if(L[1][p[mid]]<=x) l=mid;
      else r=mid;
    }
    for(pair<int,int> P=get(0,r);P.F>x;P=get(0,r)){
      //erorp(P);
      ans[P.S]=1;
      upd(pos[P.S],mp(-1,P.S));
    }
    /*f(j,0,m){
      if(L[1][p[j]]>x) break ;
      if(seg[j+m].F>x){
        ans[p[j]]=1;
        upd(j,mp(-1,-1));
      }
    }*/
    /*f(j,0,m){
      if(L[0][j]<=i && i<R[0][j] && L[1][j]<=x && x<R[1][j]){
        ans[j]=1;
      }
    }*/
  }
  return ans;
}
/*
6 6 3
3 0
3 1
3 4
1 2
2 5
5 1
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message

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:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   70 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |     ~~~~~~~~~~~~               
werewolf.cpp:70:3: note: in expansion of macro 'f'
   70 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |   ^
werewolf.cpp:134:18: warning: unused variable 'mid' [-Wunused-variable]
  134 |     int l=-1,r=m,mid;
      |                  ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73888 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Correct 35 ms 73908 KB Output is correct
4 Correct 39 ms 73884 KB Output is correct
5 Correct 34 ms 73980 KB Output is correct
6 Correct 36 ms 73984 KB Output is correct
7 Correct 33 ms 73884 KB Output is correct
8 Correct 39 ms 73932 KB Output is correct
9 Correct 38 ms 73920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73888 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Correct 35 ms 73908 KB Output is correct
4 Correct 39 ms 73884 KB Output is correct
5 Correct 34 ms 73980 KB Output is correct
6 Correct 36 ms 73984 KB Output is correct
7 Correct 33 ms 73884 KB Output is correct
8 Correct 39 ms 73932 KB Output is correct
9 Correct 38 ms 73920 KB Output is correct
10 Correct 45 ms 74644 KB Output is correct
11 Correct 44 ms 74616 KB Output is correct
12 Correct 39 ms 74572 KB Output is correct
13 Correct 40 ms 74976 KB Output is correct
14 Correct 41 ms 74728 KB Output is correct
15 Correct 47 ms 74720 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 121068 KB Output is correct
2 Correct 580 ms 123824 KB Output is correct
3 Correct 563 ms 120856 KB Output is correct
4 Correct 546 ms 119816 KB Output is correct
5 Correct 543 ms 120000 KB Output is correct
6 Correct 547 ms 120972 KB Output is correct
7 Correct 520 ms 118376 KB Output is correct
8 Correct 541 ms 123788 KB Output is correct
9 Correct 511 ms 119864 KB Output is correct
10 Correct 484 ms 118152 KB Output is correct
11 Correct 502 ms 118464 KB Output is correct
12 Correct 583 ms 118892 KB Output is correct
13 Correct 526 ms 129216 KB Output is correct
14 Correct 537 ms 129212 KB Output is correct
15 Correct 566 ms 129004 KB Output is correct
16 Correct 644 ms 129100 KB Output is correct
17 Correct 532 ms 118044 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73888 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Correct 35 ms 73908 KB Output is correct
4 Correct 39 ms 73884 KB Output is correct
5 Correct 34 ms 73980 KB Output is correct
6 Correct 36 ms 73984 KB Output is correct
7 Correct 33 ms 73884 KB Output is correct
8 Correct 39 ms 73932 KB Output is correct
9 Correct 38 ms 73920 KB Output is correct
10 Correct 45 ms 74644 KB Output is correct
11 Correct 44 ms 74616 KB Output is correct
12 Correct 39 ms 74572 KB Output is correct
13 Correct 40 ms 74976 KB Output is correct
14 Correct 41 ms 74728 KB Output is correct
15 Correct 47 ms 74720 KB Output is correct
16 Correct 579 ms 121068 KB Output is correct
17 Correct 580 ms 123824 KB Output is correct
18 Correct 563 ms 120856 KB Output is correct
19 Correct 546 ms 119816 KB Output is correct
20 Correct 543 ms 120000 KB Output is correct
21 Correct 547 ms 120972 KB Output is correct
22 Correct 520 ms 118376 KB Output is correct
23 Correct 541 ms 123788 KB Output is correct
24 Correct 511 ms 119864 KB Output is correct
25 Correct 484 ms 118152 KB Output is correct
26 Correct 502 ms 118464 KB Output is correct
27 Correct 583 ms 118892 KB Output is correct
28 Correct 526 ms 129216 KB Output is correct
29 Correct 537 ms 129212 KB Output is correct
30 Correct 566 ms 129004 KB Output is correct
31 Correct 644 ms 129100 KB Output is correct
32 Correct 532 ms 118044 KB Output is correct
33 Correct 646 ms 126912 KB Output is correct
34 Correct 342 ms 112008 KB Output is correct
35 Correct 721 ms 129480 KB Output is correct
36 Correct 685 ms 127032 KB Output is correct
37 Correct 684 ms 128764 KB Output is correct
38 Correct 672 ms 127556 KB Output is correct
39 Correct 656 ms 136104 KB Output is correct
40 Correct 618 ms 130164 KB Output is correct
41 Correct 602 ms 126144 KB Output is correct
42 Correct 551 ms 123156 KB Output is correct
43 Correct 715 ms 132272 KB Output is correct
44 Correct 649 ms 126932 KB Output is correct
45 Correct 510 ms 136272 KB Output is correct
46 Correct 534 ms 136192 KB Output is correct
47 Correct 619 ms 134244 KB Output is correct
48 Correct 559 ms 134108 KB Output is correct
49 Correct 589 ms 134176 KB Output is correct
50 Correct 608 ms 134052 KB Output is correct
51 Correct 588 ms 127848 KB Output is correct
52 Correct 546 ms 127828 KB Output is correct