oj.uz

Submission #1013662

# Submission time Handle Problem Language Result Execution time Memory
1013662 2024-07-03T18:53:01 Z MarwenElarbi Werewolf (IOI18_werewolf) C++17
49 / 100
 2204 ms 252632 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
int n;
int segtree[nax*4][2];
int tab[nax];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos][0]=segtree[pos][1]=tab[l];
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
int query0(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 1e9;
    if(l>=left&&r<=right) return segtree[pos][0];
    int mid=(r+l)/2;
    return min(query0(pos*2+1,l,mid,left,right),query0(pos*2+2,mid+1,r,left,right));
}
int query1(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos][1];
    int mid=(r+l)/2;
    return max(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int bs_min_left(int x,int cur){
    int l=-1;
    int r=x;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query0(0,0,n-1,mid,x)>=cur)
            r=mid;
        else l=mid;
    }
    return r;
}
int bs_min_right(int x,int cur){
    int l=x;
    int r=n;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query0(0,0,n-1,x,mid)>=cur)
            l=mid;
        else r=mid;
    }
    return l;
}
int bs_max_left(int x,int cur){
    int l=-1;
    int r=x;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query1(0,0,n-1,mid,x)<=cur)
            r=mid;
        else l=mid;
    }
    return r;
}
int bs_max_right(int x,int cur){
    int l=x;
    int r=n;
    while(r-l>1){
        int mid=(r+l)/2;
        if (query1(0,0,n-1,x,mid)<=cur)
            l=mid;
        else r=mid;
    }
    return l;
}
set<int> mergesort[nax*4];
void build_mergesort(int pos,int l,int r){
    if(l==r){
        mergesort[pos].insert(tab[l]);
        return;
    }
    int mid=(r+l)/2;
    build_mergesort(pos*2+1,l,mid);
    build_mergesort(pos*2+2,mid+1,r);
    for(auto u:mergesort[pos*2+1]) mergesort[pos].insert(u);
    for(auto u:mergesort[pos*2+2]) mergesort[pos].insert(u);
    return;
}
bool query(int pos,int l,int r,int left,int right,pair<int,int> cur){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right){
        return *mergesort[pos].lower_bound(cur.fi)<=cur.se;
    }
    int mid=(r+l)/2;
    return query(pos*2+1,l,mid,left,right,cur)|query(pos*2+2,mid+1,r,left,right,cur);
}
int t=0;
int conv[nax];
void dfs(int x,int p){
    conv[x]=t;
    tab[t++]=x;
    for(auto u:adj[x]){
        if(u==p) continue;
        dfs(u,x);
    }
    return;
}
vector<int> mn(nax);
vector<int> mx(nax);
bool vis[nax];
void min_djikastra(int x){
    priority_queue<int> pq;
    pq.push(x);
    mn[x]=x;
    vis[x]=true;
    while(!pq.empty()){
        int node=pq.top();
        pq.pop();
        for(auto u:adj[node]){
            if(vis[u]) continue;
            vis[u]=true;
            mn[u]=min(u,mn[node]);
            pq.push(u);
        }
    }
}
void max_djikastra(int x){
    priority_queue<int,vector<int>,greater<int>> pq;
    pq.push(x);
    mx[x]=x;
    vis[x]=true;
    while(!pq.empty()){
        int node=pq.top();
        pq.pop();
        for(auto u:adj[node]){
            if(vis[u]) continue;
            vis[u]=true;
            mx[u]=max(u,mx[node]);
            pq.push(u);
        }
    }
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q=R.size();
    int M=X.size();
    if(N<=3e3+5&&M<=6e3+5&&Q<=3e3+5){
        n=N;
        for (int i = 0; i < (int)X.size(); ++i)
        {
            adj[X[i]].pb(Y[i]);
            adj[Y[i]].pb(X[i]);
        }
        vector<int> ans;
        
        for (int i = 0; i < Q; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                mn[j]=1e9;
                mx[j]=-1e9;
                vis[j]=0;
            }
            min_djikastra(S[i]);
            for (int j = 0; j < N; ++j)
            {
                vis[j]=0;
            }
            max_djikastra(E[i]);
            pair<int,int> cur={L[i],R[i]};
            bool test=false;
            for (int j = L[i]; j < R[i]+1; ++j)
            {
                if(cur.fi<=mn[j]&&mx[j]<=cur.se){
                    test=true;
                }
                if(test) break;
            }//cout <<endl;
            ans.pb((test==true ? 1 : 0));
        }
        return ans;
    }else{
        n=N;
        int q=R.size();
        int v[n];
        memset(v,0,sizeof v);
        for (int i = 0; i < n-1; ++i)
        {
            adj[X[i]].pb(Y[i]);
            adj[Y[i]].pb(X[i]);
            v[X[i]]++;
            v[Y[i]]++;
        }
        int lst;
        for (int i = 0; i < n; ++i)
        {
            if(v[i]==1){
                lst=i;
            }
        }
        dfs(lst,-1);
        build(0,0,n-1);
        build_mergesort(0,0,n-1);
        vector<int> ans;
        for (int i = 0; i < q; ++i)
        {
            pair<int,int> cur={L[i],R[i]};
            S[i]=conv[S[i]];
            E[i]=conv[E[i]];
            bool test=(E[i]>=S[i]);
            pair<int,int> cnt;
            if(test){
                int right=bs_min_right(S[i],cur.fi);
                int left=bs_max_left(E[i],cur.se);
                cnt={right,left};
            }else{
                int right=bs_min_left(S[i],cur.fi);
                int left=bs_max_right(E[i],cur.se);
                cnt={left,right};
            } 
           
            if(cnt.fi<cnt.se){
                ans.pb(0);
                continue;
            }
            ans.pb((query(0,0,n-1,cnt.se,cnt.fi,cur)) ? 1 : 0);
        }
        return ans;
    }
    
}

/*namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}*/

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:208:12: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  208 |         dfs(lst,-1);
      |         ~~~^~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44308 KB Output is correct
2 Correct 17 ms 44308 KB Output is correct
3 Correct 20 ms 44124 KB Output is correct
4 Correct 17 ms 44284 KB Output is correct
5 Correct 17 ms 44304 KB Output is correct
6 Correct 17 ms 44300 KB Output is correct
7 Correct 18 ms 44124 KB Output is correct
8 Correct 18 ms 44120 KB Output is correct
9 Correct 17 ms 44124 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44308 KB Output is correct
2 Correct 17 ms 44308 KB Output is correct
3 Correct 20 ms 44124 KB Output is correct
4 Correct 17 ms 44284 KB Output is correct
5 Correct 17 ms 44304 KB Output is correct
6 Correct 17 ms 44300 KB Output is correct
7 Correct 18 ms 44124 KB Output is correct
8 Correct 18 ms 44120 KB Output is correct
9 Correct 17 ms 44124 KB Output is correct
10 Correct 1183 ms 44652 KB Output is correct
11 Correct 1022 ms 44660 KB Output is correct
12 Correct 319 ms 44632 KB Output is correct
13 Correct 1097 ms 44632 KB Output is correct
14 Correct 954 ms 44632 KB Output is correct
15 Correct 1331 ms 44636 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1741 ms 252396 KB Output is correct
2 Correct 2142 ms 252632 KB Output is correct
3 Correct 2204 ms 252364 KB Output is correct
4 Correct 2162 ms 252372 KB Output is correct
5 Correct 2193 ms 252380 KB Output is correct
6 Correct 2039 ms 252376 KB Output is correct
7 Correct 1846 ms 252284 KB Output is correct
8 Correct 2074 ms 252448 KB Output is correct
9 Correct 1396 ms 252620 KB Output is correct
10 Correct 1614 ms 252364 KB Output is correct
11 Correct 1712 ms 252628 KB Output is correct
12 Correct 1574 ms 252364 KB Output is correct
13 Correct 1893 ms 252516 KB Output is correct
14 Correct 2001 ms 252492 KB Output is correct
15 Correct 1935 ms 252400 KB Output is correct
16 Correct 2007 ms 252364 KB Output is correct
17 Correct 1907 ms 252392 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44308 KB Output is correct
2 Correct 17 ms 44308 KB Output is correct
3 Correct 20 ms 44124 KB Output is correct
4 Correct 17 ms 44284 KB Output is correct
5 Correct 17 ms 44304 KB Output is correct
6 Correct 17 ms 44300 KB Output is correct
7 Correct 18 ms 44124 KB Output is correct
8 Correct 18 ms 44120 KB Output is correct
9 Correct 17 ms 44124 KB Output is correct
10 Correct 1183 ms 44652 KB Output is correct
11 Correct 1022 ms 44660 KB Output is correct
12 Correct 319 ms 44632 KB Output is correct
13 Correct 1097 ms 44632 KB Output is correct
14 Correct 954 ms 44632 KB Output is correct
15 Correct 1331 ms 44636 KB Output is correct
16 Correct 1741 ms 252396 KB Output is correct
17 Correct 2142 ms 252632 KB Output is correct
18 Correct 2204 ms 252364 KB Output is correct
19 Correct 2162 ms 252372 KB Output is correct
20 Correct 2193 ms 252380 KB Output is correct
21 Correct 2039 ms 252376 KB Output is correct
22 Correct 1846 ms 252284 KB Output is correct
23 Correct 2074 ms 252448 KB Output is correct
24 Correct 1396 ms 252620 KB Output is correct
25 Correct 1614 ms 252364 KB Output is correct
26 Correct 1712 ms 252628 KB Output is correct
27 Correct 1574 ms 252364 KB Output is correct
28 Correct 1893 ms 252516 KB Output is correct
29 Correct 2001 ms 252492 KB Output is correct
30 Correct 1935 ms 252400 KB Output is correct
31 Correct 2007 ms 252364 KB Output is correct
32 Correct 1907 ms 252392 KB Output is correct
33 Incorrect 1735 ms 251624 KB Output isn't correct
34 Halted 0 ms 0 KB -