oj.uz

Submission #805187

# Submission time Handle Problem Language Result Execution time Memory
805187 2023-08-03T13:51:03 Z gagik_2007 Werewolf (IOI18_werewolf) C++17
15 / 100
 488 ms 125336 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool used2[N];
ll tl[N][LG];
ll th[N][LG];

void dfs1(int v, int btm){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]&&to>=btm){
            dfs1(to,btm);
        }
    }
}

bool dfs2(int v, int top){
    if(used[v])return true;
    used2[v]=true;
    for(int to:g[v]){
        if(!used2[to]&&to<=top){
            if(dfs2(to,top)){
                return true;
            }
        }
    }
    return false;
}

void get_chain(int v, int par, vector<int>&ch){
    ch.push_back(v);
    for(int to:g[v]){
        if(to!=par){
            get_chain(to,v,ch);
        }
    }
}

void build_ST(vector<int>&a){
    for(int i=0;i<a.size();i++){
        tl[i][0]=a[i];
        th[i][0]=a[i];
    }
    for(int j=1;j<LG;j++){
        for(int i=0;i+(1<<(j-1))<a.size();i++){
            tl[i][j]=min(tl[i][j-1],tl[i+(1<<(j-1))][j-1]);
            th[i][j]=max(th[i][j-1],th[i+(1<<(j-1))][j-1]);
        }
    }
}

ll get_highest(int l, int r){
    int len=r-l+1;
    int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
    return max(th[l][lgf],th[r-(1<<lgf)][lgf]);
}

ll get_lowest(int l, int r){
    int len=r-l+1;
    int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
    return min(tl[l][lgf],tl[r-(1<<lgf)][lgf]);
}

vector<int> check_validity(int NN, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n=NN;
    m=X.size();
    k=S.size();
    for(int i=0;i<m;i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int>ans;
    if(n<=3000&&k<=3000&&m<=6000){
        for(int i=0;i<k;i++){
            dfs1(S[i],L[i]);
            ans.push_back(dfs2(E[i],R[i]));
            fill(used,used+n+1,false);
            fill(used2,used2+n+1,false);
        }
        return ans;
    }
    int start=-1;
    for(int v=0;v<n;v++){
        if(g[v].size()==1){
            start=v;
            break;
        }
    }
    vector<int>ch;
    // cout<<"FIN1"<<endl;
    get_chain(start, start, ch);
    // cout<<"FIN2"<<endl;
    build_ST(ch);
    // cout<<"FIN3"<<endl;
    vector<int>revch(ch.size(),0);
    for(int i=0;i<ch.size();i++){
        revch[ch[i]]=i;
    }
    // for(int x:revch)cout<<x<<" ";
    // cout<<endl;
    for(int i=0;i<k;i++){
        int v=revch[S[i]];
        int u=revch[E[i]];
        // cout<<v<<" "<<u<<endl;
        if(v<u){
            int l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_lowest(v,mid)>=L[i]){
                    l=mid+1;
                }
                else{
                    r=mid;
                }
            }
            int leftbound=l-1;
            l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_highest(mid,u)<=R[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(leftbound>=l-1){
                ans.push_back(1);
            }
            else{
                ans.push_back(0);
            }
        }
        else{
            swap(v,u);
            int l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_highest(v,mid)<=R[i]){
                    l=mid+1;
                }
                else{
                    r=mid;
                }
            }
            int leftbound=l-1;
            l=v,r=u+1;
            while(l<r){
                int mid=(l+r)/2;
                if(get_lowest(mid,u)>=L[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(leftbound>=l-1){
                ans.push_back(1);
            }
            else{
                ans.push_back(0);
            }
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void build_ST(std::vector<int>&)':
werewolf.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:62:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i=0;i+(1<<(j-1))<a.size();i++){
      |                     ~~~~~~~~~~~~^~~~~~~~~
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:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<ch.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7288 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7352 KB Output is correct
7 Correct 4 ms 7356 KB Output is correct
8 Correct 4 ms 7348 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7288 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7352 KB Output is correct
7 Correct 4 ms 7356 KB Output is correct
8 Correct 4 ms 7348 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 114 ms 7744 KB Output is correct
11 Correct 70 ms 7704 KB Output is correct
12 Correct 10 ms 7880 KB Output is correct
13 Correct 106 ms 7752 KB Output is correct
14 Correct 79 ms 7716 KB Output is correct
15 Correct 158 ms 7884 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 488 ms 125336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7288 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7352 KB Output is correct
7 Correct 4 ms 7356 KB Output is correct
8 Correct 4 ms 7348 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 114 ms 7744 KB Output is correct
11 Correct 70 ms 7704 KB Output is correct
12 Correct 10 ms 7880 KB Output is correct
13 Correct 106 ms 7752 KB Output is correct
14 Correct 79 ms 7716 KB Output is correct
15 Correct 158 ms 7884 KB Output is correct
16 Incorrect 488 ms 125336 KB Output isn't correct
17 Halted 0 ms 0 KB -