oj.uz

답안 #585913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585913 2022-06-29T14:31:29 Z Koosha_mv 늑대인간 (IOI18_werewolf) C++14
34 / 100
 633 ms 134104 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,t,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+t]=val;
  for(x+=t;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+=t,r+=t;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,t=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,t){
    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,t){
    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(t);
  iota(all(p),0);
  sort(all(p),[&](int u,int v){ return L[1][u]<L[1][v]; });
  f(i,0,t) pos[p[i]]=i;
  f(i,0,t){
    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=n,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));
    }
  }
  return ans;
}
/*
6 6 3
3 0
3 1
3 4
1 2
2 5
5 1
4 2 2 2
5 4 3 4
4 2 1 2
*/

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=n,mid;
      |                  ^~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Incorrect 35 ms 73872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Incorrect 35 ms 73872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 577 ms 121524 KB Output is correct
2 Correct 617 ms 128416 KB Output is correct
3 Correct 551 ms 125472 KB Output is correct
4 Correct 613 ms 124552 KB Output is correct
5 Correct 569 ms 124528 KB Output is correct
6 Correct 633 ms 125524 KB Output is correct
7 Correct 562 ms 122916 KB Output is correct
8 Correct 554 ms 128512 KB Output is correct
9 Correct 515 ms 124560 KB Output is correct
10 Correct 503 ms 122640 KB Output is correct
11 Correct 550 ms 123296 KB Output is correct
12 Correct 540 ms 123736 KB Output is correct
13 Correct 542 ms 134048 KB Output is correct
14 Correct 584 ms 134104 KB Output is correct
15 Correct 567 ms 134088 KB Output is correct
16 Correct 580 ms 134080 KB Output is correct
17 Correct 507 ms 123008 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 73932 KB Output is correct
2 Correct 34 ms 73996 KB Output is correct
3 Incorrect 35 ms 73872 KB Output isn't correct
4 Halted 0 ms 0 KB -