oj.uz

답안 #585927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585927 2022-06-29T14:47:51 Z Koosha_mv 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 120400 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

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 35 ms 73956 KB Output is correct
3 Correct 35 ms 74028 KB Output is correct
4 Correct 36 ms 73872 KB Output is correct
5 Correct 37 ms 73928 KB Output is correct
6 Correct 36 ms 73980 KB Output is correct
7 Correct 41 ms 73932 KB Output is correct
8 Correct 35 ms 73960 KB Output is correct
9 Correct 35 ms 73932 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 35 ms 73956 KB Output is correct
3 Correct 35 ms 74028 KB Output is correct
4 Correct 36 ms 73872 KB Output is correct
5 Correct 37 ms 73928 KB Output is correct
6 Correct 36 ms 73980 KB Output is correct
7 Correct 41 ms 73932 KB Output is correct
8 Correct 35 ms 73960 KB Output is correct
9 Correct 35 ms 73932 KB Output is correct
10 Correct 48 ms 74700 KB Output is correct
11 Correct 46 ms 74656 KB Output is correct
12 Correct 43 ms 74692 KB Output is correct
13 Correct 44 ms 74844 KB Output is correct
14 Correct 50 ms 74764 KB Output is correct
15 Correct 46 ms 74736 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 120400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 35 ms 73956 KB Output is correct
3 Correct 35 ms 74028 KB Output is correct
4 Correct 36 ms 73872 KB Output is correct
5 Correct 37 ms 73928 KB Output is correct
6 Correct 36 ms 73980 KB Output is correct
7 Correct 41 ms 73932 KB Output is correct
8 Correct 35 ms 73960 KB Output is correct
9 Correct 35 ms 73932 KB Output is correct
10 Correct 48 ms 74700 KB Output is correct
11 Correct 46 ms 74656 KB Output is correct
12 Correct 43 ms 74692 KB Output is correct
13 Correct 44 ms 74844 KB Output is correct
14 Correct 50 ms 74764 KB Output is correct
15 Correct 46 ms 74736 KB Output is correct
16 Execution timed out 4062 ms 120400 KB Time limit exceeded
17 Halted 0 ms 0 KB -