# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130600 | sealnot123 | Werewolf (IOI18_werewolf) | C++14 | 857 ms | 122796 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
typedef vector<int> VI;
const int N = 200005, Q = 400005;
int n, q, m;
struct A{
int q, u, t;
bool operator <(const A& o) const{
return t<o.t;
}
};
vector<int> g[N], G[N], ans;
vector<A> H, WW;
int P[Q], sz[Q], ll[Q], rr[Q], p[N], dp[N], T;
int st[N], en[N];
set<int> node[N];
set<int>::iterator IT;
int fin(int i){
if(p[i]==i) return i;
return fin(p[i]);
}
void merg(int a, int b, bool ww){
a = fin(a); b = fin(b);
if(a == b) return ;
if(dp[a]<dp[b]) swap(a,b);
if(!ww) G[a].pb(b);
else{
for(int it : node[b]) node[a].insert(it);
}
p[b] = a;
dp[a] += dp[b];
}
void dfs(int u){
st[u] = ++T;
for(int e : G[u]) dfs(e);
en[u] = T;
}
VI check_validity(int nn, VI X, VI Y, VI S, VI E, VI L, VI R) {
q = SZ(S);
n = nn;
m = SZ(X);
ans.resize(q);
int i,j,k,l,a,b,c,d;
for(i=0;i<m;i++){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
for(i=0;i<q;i++){
H.pb({i, X[i], -L[i]});
WW.pb({i, Y[i], R[i]});
}
sort(all(H)); sort(all(WW));
// human preparation
int nw;
nw = q-1;
for(i=0;i<n;i++) p[i]=i, dp[i]=1;
for(i=n-1;i>=0;i--){
for(int e : g[i]){
if(e > i) merg(i,e,false);
}
while(nw>=0 && H[nw].t == -i){
P[H[nw].q] = fin(H[nw].u);
sz[H[nw].q] = dp[P[H[nw].q]];
nw--;
}
}
for(i=0;p[i]!=i;i++);
dfs(i);
for(i=0;i<q;i++){
ll[i] = st[P[i]];
rr[i] = st[P[i]]+sz[i]-1;
}
// werewolf prepareation
nw=0;
for(i=0;i<n;i++){
p[i] = i; dp[i] = 1;
node[i].insert(st[i]);
}
for(i=0;i<n;i++){
for(int e : g[i]){
if(e < i) merg(i, e, true);
}
while(nw<q && WW[nw].t == i){
a = fin(WW[nw].u);
b = WW[nw].q;
IT = node[a].lower_bound(ll[b]);
if(IT != node[a].end() && *IT <= rr[b]) ans[b] = 1;
nw++;
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |